AllPairsShortestPaths - Algoviz Wiki

Works

Yes

Description

Visualization of Floyd's all-pairs 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 a 2D array showing the algorithm's currently computed shortest distances. The explanation pages are a pretty good supplement to the AV (and vice versa). Students might still have a little bit of difficulty understanding the concept of the "k paths", and there is no reference to dynamic programming, which would be helpful.

Step Control; Questions; Canned Data

Self Study; Lab Exercise

Screenshots

Videos

References

http://www.animal.ahrgr.de/showAnimationDetails.php3?anim=21; http://www.animal.ahrgr.de/showAnimationDetails.php3?anim=71

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 this AV. Some Jhave AVs include a tutorial on how the AV itself or the underlying algorithm works. At the bottom are links to the AV (you can run 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

AllPairsShortestPaths

Community

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

Comments

Edit

You may edit this entry if you have an account.

Animal - Floyd's Algorithm

Recommendation

Has Potential

Link

Delivery Method

Animal Animation

License

Non-Commercial

Language

English; German

Author

André Flöper

Institution

TU Darmstadt, Darmstadt, Germany

Project

Animal

Works

Yes

Description

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

Evaluation

Clear presentation. Standard presentation showing a 2D array that updates distances for each node visited. There isn't much explanation for what is going on though, and the user will need to come to this presentation with some understanding of how the algorithm works.

Animation; Step Control; Canned Data

Lecture Aid; Self Study

Screenshots

Videos

References

http://www.cs.usfca.edu/galles/visualization/download.html

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

AllPairsShortestPaths

Community

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

Comments

Edit

You may edit this entry if you have an account.

Data Structure Visualization - Floyd/Warshall All-Pairs Shortest Paths

Recommendation

Has Potential

Link

Delivery Method

Java Application

License

Unlicensed Sourcecode

Language

English

Author

David Galles

Institution

University of San Francisco

Project

Data Structure Visualization

Works

Yes

Description

Shows Floyd's algorithm for all-pairs shortest paths using dynamic programming.

Evaluation

Reasonable attempt to demonstrate what is not the easiest algorithm to visualize. The table updates could be more clear, and step-by-step explanations, perhaps with pseudocode, are needed.

Animation; Step Control; Random Data

Lecture Aid; Self Study

Screenshots

Videos

References

First Visited

2006-09-01

Last Visited

2008-07-02

Last Updated

2006-04-05

Topic

AllPairsShortestPaths

Community

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

Comments

Edit

You may edit this entry if you have an account.

GALGO - Floyd'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 Floyd's all-pairs shortest paths algorithm on it. A separate window shows the table for the shortest path distances. At each iteration, the two boxes in the table that contribute to the current distance are indicated.

Evaluation

Sophisticated graph editing capabilities. The AV portion is a straight animation.

Exploring the Concept

Screenshots

Videos

References