uweschmidt.org

42 / π ≈ 13.37 

DijkstraVis

This software was made for a course project. We were given the task to develop a program which interactively visualizes Dijkstra’s algorithm for beginners. We were not supposed to focus on rigorous teaching of the algorithm. First of all, the program should be appealing to people without prior knowledge of computer science. It should keep their attention and convey the message that computers actually make our daily live easier (at least in some regards) by putting Dijkstra’s algorithm into context.

Some of the technical requirements were to provide a graph editor with additional random graph generation and the possibility to save and load graphs. The user should have the possibility to step through the algorithm (forward and backward). Each step the progress made by the algorithm should be reflected by coloring the graph and presenting detail information (on demand).

Download

29 Responses

  1. penjuin says:
    Thanks!

    Thanks a bunch for this. It is a really useful program!

  2. ripple says:
    great help indeed…

    Thank you! That was a great illustration..! Very nice indeed!

  3. Anonymous says:
    Really helped my understanding

    I couldn’t find a good explanation of this algorithm, but with your program, I was able to make sense of Wikipedia’s. Thanks.

  4. Anonymous says:
    thx

    thx

  5. David.P says:
    Amazing, perfect work!

    Amazing, perfect work! Thanks!

  6. Anonymous says:
    Nice work. One quick comment

    Nice work. One quick comment … in the “where is it used” section it mentions that Dijkstra’s algorithm isn’t used in this form for Google Maps. A bit more information would be helpful then because it begs the question of what algorithm is being used in Google Maps and similar. It kind of seems like the “where is it used” question gets left unanswered but we get a bit of an idea of how it could be used …

  7. Uwe says: in reply to Anonymous
    Re: Nice work. One quick comment

    I get your point, this could have been explained more clearly.

    I don’t know the details about the algorithm(s) used in Google Maps. But you can get more information by reading this informative Google blog post and their publications on the subject.
    Another real-world application of Dijkstra’s algorithm is the Open Shortest Path First-protocol used for routing in IP-networks.

    Uwe

  8. Nanni says:
    background image

    Hello,
    …and many thanks for the nice program:), but,
    please, make New York map ‘visible’, so anyone can understand how to edit the XML file (which one? I’m still experimenting with all 4’s I have) just changing the background attribute(?) or the CSS file(?)…
    Have nice days and, if you wish, thanks in advance for you reply.

    Nanni Manca

  9. Uwe says: in reply to Nanni
    Re: background image

    Hi Nanni,

    [...] please, make New York map ‘visible’, so anyone can understand how to edit the XML file (which one? I’m still experimenting with all 4’s I have) just changing the background attribute(?) or the CSS file(?)…

    I assume you want to change the graph background of a saved graph. You don’t need to edit any of the XML files in order to do that; and there are no CSS files involved whatsoever.
    From the included documentation.pdf, section 3.5: “Adding a graph background is as simple as unzipping with a standard archive program, adding a PNG background image and zipping all files again.”

    Let’s have a look at the New York example graph:

    $ unzip -l nyc.zip
    Archive:  nyc.zip
      Length     Date   Time    Name
     --------    ----   ----    ----
        27173  03-30-08 23:08   NodesAndConnections.xml
        26949  03-30-08 23:08   NodeLocations.xml
         4162  03-30-08 23:08   IntermediateNodes.xml
           13  03-30-08 23:08   StartNode.xml
         1094  03-30-08 23:08   NodeNames.xml
       255607  03-30-08 23:08   GraphBackground.png
     --------                   -------
       314998                   6 files
    

    You just need to add a PNG image file to the archive, the image’s name doesn’t matter.

    Uwe

  10. Daniel says:
    Good work!

    Hey, this app is pretty good!
    actually helped me alot to understand this algorithm!
    good work!

  11. Anonymous says:
    Thanks!! a trillion,

    Thanks!! a trillion, developers.

  12. santhosh R says:
    Its a great job. its very

    Its a great job. its very useful to me…

  13. Ken says:
    useful

    Very very useful

  14. John H says:
    Good work!

    Really, really helpful and efficient way to learn the algorithm.

  15. Akshay says:
    Data Structure

    HI your program is great!!
    I was wondering how you organised all the data about the nodes and edges i.e the position of the nodes and weight of the edges.
    How did you structure your database.
    Please your reply is very important.

  16. Uwe says: in reply to Akshay
    Re: Data Structure

    Hi Akshay,

    if you haven’t done so please read the included documentation to get a high level overview of the code.
    The interfaces for the graph, nodes and edges are in package org.uweschmidt.dijkstravis.graph, with implementations in package org.uweschmidt.dijkstravis.graph.jung.
    The positions of the nodes are managed by the JUNG2 graph library (see JavaDoc). The edge weights are automatically set to the euclidean distance (see org.uweschmidt.dijkstravis.gui.jung.transformer.MyEdgeLabelTransformer).

    I hope that helps and sorry for the late reply,
    Uwe

  17. Sören says:
    Genial

    Vielen Dank. :-)

  18. Radi says:

    Hi,

    Download broken. Du bist bei Wikipedia verlinkt, da kommt das nicht so gut ;-) .

    Radi

  19. Uwe says: in reply to Radi

    Thanks for letting me know, it’s fixed now.

    Uwe

  20. Max says:

    Thank you so much, helped me a lot for my studies. Max, Dortmund, Germany

  21. Mani says:

    Amazing job!

    My question is that how can I change the background with a map (.png) ?
    I tried it with changing the png file in New york example , but an error appeared .
    (I tried putting it with the same name as the original file , but it didn’t work).

    THANKS A LOT !

  22. Uwe says: in reply to Mani

    Hi Mani,

    what kind of error does appear? Please have a look at this previous comment where I explained how to change the background.

    Sorry for the late reply.

  23. Mani says: in reply to Uwe

    Thanks Uwe , for replying

    I followed the instruction :

    1-I saved a png file in “ny” file (tried with same name as the original one)
    2-I zipped it again and opened it from dijkstraVis

    And same error every time .

    but all the times this error appears : “Error loading file”

  24. Uwe says: in reply to Mani

    Hi Mani, please send me the files and I’ll have a look at it.

  25. mahsa says:

    hi
    i want me to alghoritm dijkstra routing in to network on chip
    what should work to alghoritm dijkstra in to routing?

  26. Jongo says:

    Sehr schönes Tool, dass die komplexen Schritte des Djikstra-Algorithmus visualisiert. Das sollte mir für die Klausur nächste Woche helfen! ;)

  27. ایمان says:

    بسیار عالی بود. ممنون

  28. jafar says:

    your program helped me many to understand dikestra algorithm
    i know that you have very thought arrounding of this program and very tried

    EXCUSE ME , i am iranian and my english language is weak
    so
    really i don’t know how thank you only i can say that you are an expert man;

    i enjoyed; you have creatted this program and my god means “ALLAH” creatted all of us and world and brain and men & women and creatted thinking power in human also; any time don’t forget god because all of time “ALLAH” help’s us ….

  29. Pan says:

    Realy nice man. Thanks

Leave a Reply