-- Dijkstra -- This is a demonstration of an algorithm to find the shortest path from a given starting point through a "graph", which is a set of nodes connected by edges. Each edge defines a specific distance between two nodes. A picture makes this clearer. Boston ------(20)---- Chicago -----(40)---- LA | | | | (16) | (10) | | | | | NewYork --------(5)---- WashingtonDC-------+ Give a starting point (Boston, say) then Dikekstra's algorithm is a method for finding the shortest path to each point. For a tiny graph like the one above this is simple, but for a larger on it gets tricker. You can find lots of online examples by typing "Dijekstra" into Google. ------------------------------------------------------------ What's Here Java sources: Dijekstra.java main() source file ReadData.java contains the method which reads in the data (duh) Node.java one node in the graph, with a list of its Edges Edge.java one edge in the graph, which connects two Nodes Graph.java data for the whole graph, including a list of Nodes Documentation compile-run A script that executes the program *.html HTML formatted versions of the .java source files api/ javadoc documentation README.txt You're looking at it. (README.txt files are also displayed in HTML directory listings.) Other *.class The typical java class files. Dijekstra-out.txt Output from running the program in verbose mode. compile-run script to do everything (You can invoke it from the command line by by typing "./compile-run" without quotes.) g5.obj The data defining the nodes. ------------------------------------------------------------ Your Projects These files were also put together as an example of what your end of term projects might look like. Note the code itself, but the structure what I've done. In particular, the documentation here illustrates much of what a project should contain. Some of the typical parts include * A birds-eye roadmap "readme" file like this one, * Interface specifications for how each part is used, * Source code, * Instructions on how to compile and run it, * Sample output (and input if need be), * Implementation comments within the code itself, * Version information and history, * Testing suites ( i.e. TestNode.java, TestGraph.java, ... ) * as well as any references and discussion you wish to include. I haven't put up tests because (a) I had a model to follow, (b) I had testing (verbose) code integrated with the code itself, and (c) it's a fairly short project. And there's not much version or history comments here, either, because I threw all this up one night. ------------------------------------------------------------ Some details of the project The Edge, Node, and Graph objects hold the data for the graph. Essentially the Graph contains an array of Nodes, and each Node contains an array of Edges which start at that Node. Each of these also has various methods to get and set its data, as well as methods to display what they look like. The data classes also have a few more properties, for example the Nodes have a color (BLACK or WHITE) to indicate whether we have a shortest path to them already or not as the algorithm progresses. I'm using the ArrayList class from java.util for the arrays here, which are a bit more powerful than the bare Object[] arrays. And I'm looping over these ArrayLists with a Java object called Iterator. The Graph object class also has a getSmallestWhiteNode() method which searches through its list of nodes and returns the smallest one which is white. The ReadData class has the code which processes the g5.obj data file. This code I took almost directly from the java applet. And the Dijkstra class has the main() method to run the whole thing. --------------------------------------------------- To Do If I was going to continue with this, I'd probably use some of the graphics classes to draw the graph next, something like what the applet does. But hey - the applets already do that, right? :) --------------------------------------------------- Technical Remarks This is an O(N^2 * E) algorithm where N is the number of nodes and E is the average number of edges per node. That means it takes about N*N*E steps to finish. With a better method of searching for the smallest white node, (i.e. a priority que or something similar), it can run in O(N log(N) E). It's interesting that finding a single shortest path is no quicker than finding all of them froma given starting point. It's also interesting that this "greedy" algorithm (which always looks for the short-term best answer) gives the best solution. This can be proven mathematically. And it's *also* interesting that this task seems very similar to the traveling salesman problem - the only difference is that the salesman is looking for cycles that hit each node once and return to the start - and yet the saleman problem is one of the classic "hard" ones, which runs in O(N!) time. So there you are. ----------------------------------------------------------- References: Mastering Algorithm's with C, Kyle Louden, pg 472 and following (Description of the algorithm, implementation in C) http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/dijkstra/Dijkstra.shtml (interactive java applets and java code, I have a local copy of one of these in ../applet_one/) http://kzoo.edu/~k98mn01/dijkstra.html (Biography of Edsger Dijkstra, 1930-) --------------------------------------------------- Nov 26, 2002 Jim Mahoney (mahoney@marlboro.edu)