Disjkstra and Prim algorithms
The program demonstrates the workings of Prim and Dijkstra algorithms. Given a connected, undirected, weighted graph G,
the Prim's algorithm constructs a minimal spanning tree beginning from a given vertex V. In Dijkstra algorithm,
we specify a vertex V and then construct a tree of all the shortest distances from any other vertex A to this initial V.
Both algorithms are a standard staple in any Algorithms and Data Structures course. This is neither time nor place
to give the correct history, and/or references to the earliest and/or original papers, but a discussion of these algorithms is to be found in any
textbook for a course as above, for example in M. A. Weiss, Data Structures and Algorithm Analysis in Java, Second
edition, Addison Wesley, Chapter 9. But of course, it is in a lot of other places. I basically assume that you know how these
algorithms work, this applet essentially helps the student to visualize how these algorithms evolve as the computation goes on.
To display the algorithm, click on the bluish button, labeled "Run the program".
Depending on your security setting, a yellow bar at the top of the page may appear warning you that running this
applet ("ActiveX controls" it will say) maybe dangerous. In that case, click on this yellow bar and allow the applet to be run. Trust me. In any case,
after you click on the bluish button, the tree will appear in a separate window. You may resize the window, minimize it, in which case
its icon will appear in the bottom tray so you can restore it, or close it altogether. If this last action is taken, you must click on the bluish
button again to restore the applet.
In both algorithm, a tree is constructed
in successive steps. The initial vertex is chosen by the user, and then at every step, each algorithm adds an edge from a vertex already in the tree to
a new vertex, not in the tree. The program allows the user to watch these steps, one at a time, and to examine the tree, the graph,
and the status of the computation in-between the steps.
The graph consists of 400 vertices, arranged in a square array of size 20 by 20. The weights of the edges can be set by the user by clicking on
"Fix graph" button in the bottom panel. Four choices are offered: All edges of the same weight, two choices of some random scheme, and one
given by a formula. There is no redeeming social value in the formula, I just made it up. By default, when the program starts, all edges are assigned weight 1.
The rest is more or less self-explanatory, take it for a spin yourself. There is some discussion below of the functionality of various gadgets.
Functionality of the Buttons.
Color coding of the Display
Response to Mouse
- Fix Graph button. This sets the weight of all the edges. The choices offered
through a dialog box are as follows:
- Uniform - all edges of length 1. Results in rather boring outcomes
- Random 1 - lengths are chosen at random, in the range 1 - 10,000
- Polynomial - lengths are chosen according to the displayed formula. There
is no wisdom as to the formula, it was just made up.
- Random 2 - just like Random 1, except that after the lengths of the edges
are randomly chosen, 10% of these edges are randomly selected, and their lengths are re-set to 1.
Provides for more interesting results.
- Return to top
- Find Shortest Distance button. Finds the shortest distance between two given vertices. Dijkstra's algorithm
is used. This means that given an initial vertex V, the shortest distance
from V to every other vertex is calculated. You are prompted
to click on the source vertex, call it V and offered the choice of three possibilities:
- Slow - Manual. Pressing the space bar results in the algorithm making one pass, i.e.,
a new vertex w is chosen, and the shortest distance from V to w
is established.
- Fast - Automatic. Only the final result of the computation is shown: All the shortest paths
from all the vertices to V are displayed.
- Slow - Animation. The algorithm makes two steps per second, at each step a new vertex
w is chosen, and the intermediate results is displayed.
- Return to top
- Find Min Spanning Tree Finds the minimal spanning tree of the graph, using the Prim's algorithm.
The screen prompts for the initial vertex V and then the choice of speeds is offered as in the
case above. Three choices are given:
- Slow - Manual. Pressing the space bar results in the algorithm making one step, choosing
the next vertex, and displaying the result.
- Fast - Automatic. Only the final result of the computation is shown: The minimal
spanning tree is displayed, with root V.
- Slow - Animation. The algorithm makes two steps per second, and the intermediate results
are displayed.
- Return to top
- Finish In case the mode is slow, or automatic, pressing Finish changes the mode to fast,
the calculation is completed, and the results are displayed.
- Reset Clears the graph for the next demonstration. The weights of the
edges are not changed.
- Display of the final results. In both cases (Minimal spanning tree, and the shortest distances) a tree
is displayed, with the root (initial vertex V, shown in blue) chosen by the user.
In case of the minimal spanning tree, the total weight is also indicated. In case of Dijkstra's algorithm,
clicking (and holding) on a vertex, say w, shows the shortest path from V to w. See also the discussion of
mouse clicks.
- Display of partial results Again, in each algorithm, the partial tree is displayed
with edges in red. The candidate edges for addition are displayed in
blue, and the next vertex to be chosen is marked in red.
- Return to top
- Click on edge. At any stage of the computation, except when the program is in the animation mode, you can click on any edge,
and hold down the button. The weight of that edge will be displayed.
- Click on vertex. When calculating the shortest distance, or when such a calculation is finished, you can click
on any vertex, and the (tentative) distance to the root will be displayed, together with the (tentative) shortest path.
When the calculation is finished, all the distances and the path are no longer tentative, but represent the true
shortest paths and distances.
- Return to top
.
Any comments are always welcomed: drobot@vdrobot.com
Back to Drobot's home page