# 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

# Buttons

• 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.
• 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.
• 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.
• 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

• 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.