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

Display

Mouse

  • 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