SingleSourceShortestPaths

Works

Yes

Description

DSV provides options to run multiple instances of the application and compare various algorithms. The Dijkstra's algorithm here has randomized examples to run through the algorithm directly without constructing a graph. It contains various views such as the Logical, Adjacency List view and the Adjacency Matrix view. Bottom of the screen holds the animation and interaction controls. The animation contains a complete table that describes all the information such as the vertex, cost, path etc that is required to traverse through a graph using Dijkstra's algorithm. The animation speed can be controlled easily using the slider bar, or user can go step-by-step. The graph also highlights progress in the array for every iteration.

Evaluation

Generally good visualization. Strengths include the option to go step-by-step and skipping to the last step. The algorithm goes through every possibility through the graph and also using the table that contains all the information of every node. After every iteration nodes are updated. The Adjacency list and matrix views are helpful for seeing these representations, but not for following the algorithm. The main deficiency of this AV is lack of textual feedback for every step and a history window. But the annotations on the table at each step almost give enough information about this, which is why this AV is "Recommended". It also needs a "back" button to trace back through the steps. The tool does not highlight the final path in the graph.

Animation; Step Control; Random Data

Lecture Aid; Self Study

Screenshots

Videos

References

First Visited

2006-01-09

Last Visited

2008-07-02

Last Updated

2006-04-05

Topic

Community

Average rating:	4.0
Your rating:	You must be logged in to Rate.

http://www.animal.ahrgr.de/showAnimationDetails.php3&anim=15

Edit

You may edit this entry if you have an account.

Animal - Djikstra's Algorithm

Recommendation

Recommended

Link

Delivery Method

Animal Animation

License

Non-Commercial

Language

English; German

Author

Jens Brodowski; Jens Brodowski

Institution

TU Darmstadt, Darmstadt, Germany

Project

Animal

Works

Yes

Description

Presents a slideshow with an example walking through Djikstra's algorithm performed on a small graph.

Evaluation

Clear presentation. Standard presentation showing an array that updates distances for each node visited, one line for each node.

Animation; Step Control; Canned Data

Lecture Aid; Self Study

Screenshots

Videos

References

For detailed instructions on how to install Animal and run Animal AVs, see: http://www.algoanim.info/Animal2/?q=node/290. Once you have installed the Animal .jar file and downloaded/unpacked the .zip file of Animal animations, you are now ready to run Animal. Run the .jar file to start Animal. Then go to the "Open" menu item, and browse to where you put the animal animations you got in the .zip file. Pick this AV from the list. You can then step through the animation, or use "kiosk mode" to have the steps fed to you at a constant pace.

First Visited

2007-07-21

Last Visited

2010-02-04

Last Updated

1999-05-10

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://www.dgp.toronto.edu/people/JamesStewart/270/9798s/Laffra/DijkstraApplet.html

Edit

You may edit this entry if you have an account.

Dijkstra's Shortest Path Algorithm

Recommendation

Has Potential

Link

Delivery Method

Java Applet

License

Unlicensed Sourcecode

Language

English

Author

Carla Laffra

Institution

Pace University

Project

Works

Yes

Description

The original author does not appear to maintain this applet anywhere. The link above is to a third-party site.

Evaluation

Users can enter their own graph (and the editor for doing so is much easier to use than most such graph editors). Once entered, users can either step through or let it run in animation mode. A "step" is processing the next closest node. At each step, nodes and edges are colored depending on their processing status. The presentation is fairly clear. One major deficiency is that there is no view of the distance table.

Exploring the Concept; Debugging

Screenshots

Videos

References

First Visited

2006-03-09

Last Visited

2010-03-23

Last Updated

1996-03

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://jhave.org/learner/graphs/Dijkstra/dijkstra.php

Edit

You may edit this entry if you have an account.

JHAVÉ - Dijkstra's Algorithm

Recommendation

Has Potential

Link

Delivery Method

Java Web Start

License

CreativeCommons

Language

English

Author

Richard Teviotdale; Tom Naps

Institution

University of Wisconsin - Oshkosh

Project

JHAVÉ

Works

Yes

Description

Visualization of Djikstra's single-source shortest paths algorithm. Includes dynamically highlighted pseudo code. Associated HTML page contains an algorithm description, pseudo code, and example trace, and discussion of efficiency analysis.

Evaluation

The AV is set up as a series of "slides" in one pane, and pseudocode in the adjacent pane. As the user steps through the "slides", the associated pseudocode is highlighted. Occasional questions pop up for the user to answer. In addition to coloration for the graph as the algorithm progresses, there is an array showing the algorithm's currently computed shortest path for each node.

Step Control; Questions; Canned Data

Self Study; Lab Exercise

Screenshots

Videos

References

Clicking on the link above will take you to a login page for Jhave. If you do not want to create an account at jhave.org, use anonymous@anonymous.com as your user name and anonymous as your password when you are asked to login. You will then be taken to the Jhave page for Dijkstra's algorithm. Most of this is a tutorial on how it works. At the bottom are links to the AV itself (you can do it with a built-in quiz system on or off). The first time you try to run any Jhave exercise, you will have to download the Jhave webstart application. This should happen automatically when you click the link. (You might need to install Java WebStart if it is not on your machine.) Once you download the Jhave application, the AV should start automatically. You can then step through the AV by repeatedly clicking the right arrow button. Occasionally, you will be given a multiple-choice or short-answer question to answer.

First Visited

2008-07-08

Last Visited

2008-07-10

Last Updated

2008-07-01

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://j-algo.binaervarianz.de/

Edit

You may edit this entry if you have an account.

J-Algo Dijkstra's Algorithm

Recommendation

Unrated

Link

Delivery Method

Java Application

License

GPL

Language

German

Author

j-Algo Team

Institution

TU Dresden

Project

j-Algo

Works

Yes

Description

Dijkstra's algorithm for the single-source shortest paths problem. While the site says that the project is under GPL license, no source code was found.

Evaluation

Screenshots

Videos

References

First Visited

2009-04-23

Last Visited

2009-04-23

Last Updated

2008

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://www.cse.iitk.ac.in/users/dsrkg/cs210/applets/sp_dijkstra/Dijkstra.html

Edit

You may edit this entry if you have an account.

Ghosh - Single Source Shortest Paths

Recommendation

Has Potential

Link

Delivery Method

Java Applet

License

Unavailable

Language

English

Author

R. K. Ghosh

Institution

Indian Institute of Technology, Kanpur

Project

Ghosh's Collection

PartOfCollection

Works

Yes

Description

Step-by-step guided visualization tool. This allows user to draw their own graph or use the default graph. Then user can select the search algorithm to visualize and the start vertex and then step through it.

Evaluation

The tool introduces a good amount of interaction with the user by allowing him to draw his own graph along with weights to the edges, or use a default graph, also directing him continuously through messages displayed in the message window. However the main issue is the design of the user interface. The choice of colors is too gaudy and there seems to be too many buttons and instructions before the user can start running the actual visualization. The user has no control over the pace of the animation that takes place during each step, and it tend to be too slow. However, during the animation the informative messages describing the step are displayed for too brief a period, with the user not controlling the pacing. Therefore the user doesn’t get enough time to assimilate what has happened. It would have helped to have a history window instead of a message window. However, use of colors to represent the various states of the nodes is a plus and the explanations in the message window are sufficiently detailed. This tool is almost there but falls short because of poor user interface design.

Step Control; Animation; User Data; Canned Data

Lecture Aid; Self Study

Screenshots

Videos

References

First Visited

2006-11-06

Last Visited

2008-07-15

Last Updated

2001-08-12

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://www.cs.hut.fi/Research/TRAKLA2/exercises/Dijkstra.html

Edit

You may edit this entry if you have an account.

Trakla - Djikstra's Algorithm

Recommendation

Has Potential

Link

Delivery Method

Java Application

License

GPL

Language

English

Author

Ville Karavirta; Ari Korhonen; Lauri Malmi; Kimmo Stålnacke

Institution

Helsinki University of Technology

Project

Trakla2

Works

Yes

Description

User clicks on nodes of the graph in order that they are processed.

Evaluation

(Note that there is also a "heap version" for this exercise, but that one is incomprehensible.) This is a great idea to have users show proficiency in the algorithm by processing the graph. But the implementation does not quite work out. The big problem is that the edge distances are not shown on the graph. They are shown in an adjacency list, but it is extremely difficult for users to integrate that information to pick the next vertex. The graph layouts are poor, and it would not be a simple thing to label the edges with their distances.

Canned Data; Predictions

Lecture Aid; Self Study; Lab Exercise

Screenshots

Videos

References

First Visited

2008-07-29

Last Visited

2008-07-29

Last Updated

2006-01-25

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://links.math.rpi.edu/devmodules/graph_networking/compat/page17.html

Edit

You may edit this entry if you have an account.

ProjectLinks - Bellman/Ford Algorithm

Recommendation

Not Recommended

Link

Delivery Method

Java Applet

License

Unavailable

Language

English

Author

Institution

Rensselaer Polytechnic Institute

Project

Works

Yes

Description

Bellman-Ford algorithm to solve the single-source shortest paths problem. Unlike the better-known Dijkstra's algorithm, this will work even with edges of negative weight.

Evaluation

An animation on a pre-determined graph. Very limited. You can't even control the pacing of the animation.

Lecture Aid

Screenshots

Videos

References

First Visited

2009-04-23

Last Visited

2009-04-23

Last Updated

1998

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://links.math.rpi.edu/devmodules/graph_networking/xhtml/page14.xml

Edit

You may edit this entry if you have an account.

ProjectLinks - Dijkstra's Algorithm

Recommendation

Not Recommended

Link

Delivery Method

Java Applet

License

Unavailable

Language

English

Author

Mark Holmes; Robert Spiker; Mark Goldberg

Institution

Rensselaer Polytechnic Institute

Project

Works

Yes

Description

Dijkstra's algorithm for solving the single-source shortest paths problem. A Shockwave-like presentation with no user control or definable data sets.

Evaluation

Strengths: has pseudocode available but doesn't depend on it. (Note: Access to the pseudocode has been lost.) Weaknesses: only has Play and Pause buttons; no user-defined data sets.

Lecture Aid

Screenshots

Videos

References

First Visited

2006-04-18

Last Visited

2009-04-23

Last Updated

1999

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://students.ceid.upatras.gr/~papagel/project/kef5_7_1.htm

Edit

You may edit this entry if you have an account.

Minimum Routes Finder

Recommendation

Unrated

Link

Delivery Method

Java Applet

License

Language

English

Author

Papagelis Athanasios

Institution

University of Patras

Project

UPatras Collection

PartOfCollection

Works

Yes

Description

Fairly technical explanation and visualization. This seems to be geared towards dynamic programming and mathematics students rather than a computer science understanding.

Evaluation

Strengths: stepwise and continuous operation; random data sets. Weaknesses: no user defined data sets; may not implement Dijkstra's algorithm exactly right (or uses a shortcut not declared).

Exploring the Concept

Screenshots

Videos

References

First Visited

2006-04-18

Last Visited

2006-04-18

Last Updated

1997-10-15

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://www.cs.auckland.ac.nz/software/AlgAnim/dijkstra.html

Edit

You may edit this entry if you have an account.

Auckland - Dijkstra's Algorithm

Recommendation

Has Potential

Link

Delivery Method

Java Applet

License

Unavailable

Language

English

Author

Mervyn Ng; Woi Ang; John Morris

Institution

University of Auckland

Project

Morris' Collection

PartOfCollection

Works

Yes

Description

Typical depiction of Dijkstra's algorithm.

Evaluation

Strengths - multiple developer-defined data sets; pseudo-code follows along; stepwise and continuous operation. Weaknesses - no user-defined data sets; not clear how the nodes remember their predecessor; the algorithm presentation is just hard to follow.

Step Control; Animation; Canned Data

Lecture Aid

Screenshots

Videos

References

First Visited

2006-04-18

Last Visited

2008-07-17

Last Updated

1998

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/dijkstra/Dijkstra.shtml.en

Edit

You may edit this entry if you have an account.

Shortest Path Problem - Dijkstra's Algorithm

Recommendation

Unrated

Link

Delivery Method

Java Applet

License

Language

English

Author

Kenji Ikeda

Institution

University of Tokushima

Project

Works

Yes

Description

Easy-to-follow implementation of Dijkstra's algorithm. No controls necessary; clicking the graph works through one step of the process.

Evaluation

Strengths: easy to follow; 10 developer-supplied data sets; shows edges as either used or not used. Weaknesses: no continuous operation; no user-defined data sets

Teaching the Concept

Screenshots

Videos

References

First Visited

2006-04-18

Last Visited

2006-04-18

Last Updated

2004-09-17

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://www.ifors.ms.unimelb.edu.au/tutorial/dijkstra/island.html

Edit

You may edit this entry if you have an account.

tutORial's Shortest Path Problem

Recommendation

Unrated

Link

Delivery Method

JavaScript

License

Language

English

Author

Moshe Sniedovich

Institution

University of Melbourne

Project

Works

Yes

Description

Dijkstra's algorithm using distances between points on the Australian continent. Unlike most visualizations, this one is written in JavaScript and HTML.

Evaluation

Strengths: stepwise operation; text descriptions of each step; user can choose start and end nodes; distance between nodes denotes cost / Weaknesses: user cannot define own nodes; no continuous operation

Teaching the Concept; Exploring the Concept

Screenshots

Videos

References

First Visited

2006-04-18

Last Visited

2006-04-18

Last Updated

2000-02-15

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

Edit

You may edit this entry if you have an account.

GALGO - Dijkstra's Algorithm

Recommendation

Has Potential

Link

http://www.informatik.fb2.fh-frankfurt.de/~hoebel/graphen/galgo/ (German version); http://www.informatik.fb2.fh-frankfurt.de/~hoebel/graphen/galgo/en/index.html (English version)

Delivery Method

Java Applet

License

Unavailable

Language

German; English

Author

Natascha Hoebel; Martin Burrer

Institution

University of Applied Siences, Frankfurt

Project

GALGO

Works

Yes

Description

User either selects or creates a graph, and then runs Dijkstra's single-source shortest paths algorithm on it. A separate window shows the table for the shortest path distances.

Evaluation

Sophisticated graph editing capabilities. The AV portion is a straight animation. The English version is only partly translated.

Canned Data; Animation

Lecture Aid; Teaching the Concept

Screenshots

Videos

References

First Visited

2009-04-21

Last Visited

2009-05-01

Last Updated

2003

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://users.uom.gr/~thanasis/JAVENGA.html

Edit

You may edit this entry if you have an account.

JAVENGA Shortest Paths

Recommendation

Unrated

Link

Delivery Method

Java Applet

License

Unavailable

Language

English

Author

Baloukas Athanasios

Institution

University of Macedonia, Department of Applied Informatics, Thessaloniki, Greece

Project

JAVENGA

Works

Yes

Description

The software features static visualizations for Graph and Network Algorithms. More specifically it illustrates: BFS and DFS traversals; topological sorting; various shortest path algorithms; Minimum Spanning tree algorithms of Prim and Kruskal; and the Primal Network Simplex Algorithm for the balanced Minimum Cost Network Flow Problem.

Evaluation

Teaching the Concept; Exploring the Concept

Screenshots

Videos

References

You can use this as a Java Applet (click on link above) or get the Java .jar file at http://users.uom.gr/~thanasis/JAVENGA.html. When you open the applet, you must first enter a graph using the graphical editor (first 3 buttons at the top). You can view the graph representation (4th button). You can choose an algorithm to run (rightmost button at top). It doesn't appear that you can run an algorithm until you have actually created a graph using the editor.

First Visited

2009-09-02

Last Visited

2009-09-02

Last Updated

2009

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://alvie.algoritmica.org/

Edit

You may edit this entry if you have an account.

ALVIE - Dijkstra and Bellman-Ford Sortest Paths Algorithms

Recommendation

Unrated

Link

Delivery Method

Java Application

License

By Request

Language

English

Author

Pilu Crescenzi

Institution

University of Florence

Project

ALVIE

Works

Yes

Description

Walkthroughs on an example graph for Dijkstra's and Bellman-Ford's algorithms to solve the single-source shortest paths problem. Unlike the better-known Dijkstra's algorithm, the Bellman-Ford algorithm will work even with edges of negative weight.

Evaluation

Simple-to-use user interface for walking through the example, since a good example is already provided with the algorithm. Simply open up the AV (see directions below) and step through the example with pseudo-code. As you go through the example, you are directed to the corresponding line in the pseudocode and given a line or two of explanation in the message window. Attractive layout of the data, including colors indicating the current nodes being processed.

Step Control; Canned Data

Lecture Aid; Self Study

Screenshots

Videos

Bellman-Ford Dijkstra

References

Download and unzip the ALVIE system from the website. Double click on the .jar file. Within the ALVIE pane (not the GRIND pane), click on the "eye" icon (third icon from the left in the toolbar) to get a list of algorithms from which selecting the AV that you want. Once selected, click OK and step through the AV with the arrow icons.

First Visited

2010-01-28

Last Visited

2010-01-28

Last Updated

2009-12-20

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.