Dijkstra's Algorithm
I've written this in both Java and C#, but I'll start with a simple Python script that I used to sanity check the output of the Java version. It uses the implementation found in python-graph.
import gv
from pygraph.classes.graph import graph
from pygraph.algorithms.minmax import shortest_path
from pygraph.readwrite.dot import write
from string import ascii_uppercase
# Graph creation
gr = graph()
#add vertices
for i in ascii_uppercase:
if (i <= "R"): gr.add_node(i)
#add edges
gr.add_edge(("A","B"), 4)
gr.add_edge(("A","E"), 7)
gr.add_edge(("B","C"), 4)
gr.add_edge(("B","K"), 3)
gr.add_edge(("C","D"), 2)
gr.add_edge(("C","J"), 4)
gr.add_edge(("D","E"), 2)
gr.add_edge(("D","G"), 3)
gr.add_edge(("D","I"), 1)
gr.add_edge(("E","F"), 6)
gr.add_edge(("F","G"), 4)
gr.add_edge(("F","R"), 6)
gr.add_edge(("G","H"), 1)
gr.add_edge(("H","L"), 4)
gr.add_edge(("H","M"), 2)
gr.add_edge(("I","J"), 1)
gr.add_edge(("I","L"), 10)
gr.add_edge(("J","K"), 1)
gr.add_edge(("K","L"), 3)
gr.add_edge(("L","M"), 2)
gr.add_edge(("L","N"), 5)
gr.add_edge(("M","N"), 1)
gr.add_edge(("M","P"), 3)
gr.add_edge(("M","R"), 5)
gr.add_edge(("N","O"), 4)
gr.add_edge(("O","P"), 2)
gr.add_edge(("P","Q"), 7)
gr.add_edge(("P","R"), 3)
gr.add_edge(("Q","R"), 8)
# Print shortest path from each vertex
for v in ascii_uppercase:
if v <= "R":
pathdicts = shortest_path(gr, v)
print "================"
print "Shortest paths from ", v
for i in ascii_uppercase:
if i <= "R":
print pathdicts[1][i], i,
here = pathdicts[0][i]
while here is not None:
print "-->", here,
here = pathdicts[0][here]
print
The output for vertex A is this:
================ Shortest paths from A 0 A 4 B --> A 8 C --> B --> A 9 D --> E --> A 7 E --> A 13 F --> E --> A 12 G --> D --> E --> A 13 H --> G --> D --> E --> A 9 I --> J --> K --> B --> A 8 J --> K --> B --> A 7 K --> B --> A 10 L --> K --> B --> A 12 M --> L --> K --> B --> A 13 N --> M --> L --> K --> B --> A 17 O --> N --> M --> L --> K --> B --> A 15 P --> M --> L --> K --> B --> A 22 Q --> P --> M --> L --> K --> B --> A 17 R --> M --> L --> K --> B --> A
C# Implementation
This is the business end of an implementation I did in C#. I was just learning the language when I wrote this, so its not exactly my best work. I also needs to be rewritten at some point to utilize a minheap.
public List<Path> dijkstrasFrom(string vertex) {
if (!vertindexes.ContainsKey(vertex)) {
throw new ArgumentException("No Vertex " + vertex + " in this graph!");
}
var pathlist = new Dictionary<string, Path>();
var finished = new Dictionary<string, bool>();
var vertices = getVertices();
foreach (var vert in vertices) {
if (vert != vertex) {
pathlist[vert] = new Path(vert, null, Double.MaxValue);
} else {
pathlist[vert] = new Path(vert, null, 0);
}
finished[vert] = false;
}
while (true) {
Path least = new Path("infinity", null, double.MaxValue);
foreach (string vert in vertices) {
if (!finished[vert] && pathlist[vert].weight < least.weight) {
least = pathlist[vert];
}
}
if (least.from_vertex_name == "infinity") {
break;
}
int from = vertindexes[least.from_vertex_name];
string fromname = least.from_vertex_name;
finished[fromname] = true;
foreach (var pair in vertindexes) { //for all vertices
int to = pair.Value;
string toname = pair.Key;
double edgeweight = adjmatrix[from][to];
//if this edge is a shorter path, set it as the path to that vertex
if (edgeweight > 0 && !finished[toname]) {
Path oldpath = pathlist[toname];
double new_path_weight = edgeweight + least.weight;
if (new_path_weight < oldpath.weight) {
pathlist[oldpath.from_vertex_name] =
new Path(oldpath.from_vertex_name, least, new_path_weight);
}
}
}
}
List<Path> paths = new List<Path>(pathlist.Values);
paths.Sort((p1, p2) => p1.from_vertex_name.CompareTo(p2.from_vertex_name));
return paths;
}
Java Implementation
This version I did for school, using a rather old and goofy graph library that we were required not to modify. Thus the lack of generics and excess of casting and general weirdness.
public static Map<String, DijkstrasNode> dijsktras(SimpleGraph graph,
String init) {
Map<String, DijkstrasNode> results = new HashMap<String, DijkstrasNode>();
BinaryHeap heap;
Iterator iter = graph.vertices();
Vertex iterVert;
DijkstrasNode thisNode;
DijkstrasNode farNode;
Edge edge;
boolean vertInGraph = false;
// add nodes to map
while (iter.hasNext()) {
iterVert = (Vertex) iter.next();
thisNode = new DijkstrasNode();
thisNode.setCurrentVertex(iterVert);
thisNode.setPreviousVertex(null);
thisNode.setKnown(false);
if (iterVert.getName().equals(init)) {
// this is the initial vertex
thisNode.setLabel(0);
vertInGraph = true;
} else {
thisNode.setLabel(Integer.MAX_VALUE);
}
results.put(iterVert.getName().toString(), thisNode);
}
// Stop now if we never found the init vertex
if (!vertInGraph) {
throw new IllegalArgumentException("Given vertex " + init
+ " not found in graph");
}
//add nodes to heap
heap = BinaryHeap.buildHeap(results.values().toArray(new DijkstrasNode[0]));
// Iterate over all vertices
while (!heap.isEmpty()) {
try {
thisNode = (DijkstrasNode) heap.deleteMin();
} catch (EmptyHeapException e) {
throw new IllegalStateException("Horrific failure of BinHeap");
}
thisNode.setKnown(true);
iter = graph.incidentEdges(thisNode.getCurrentVertex());
// Iterate over edges adjacent to this vertex.
while (iter.hasNext()) {
edge = (Edge) iter.next();
iterVert = graph.opposite(thisNode.getCurrentVertex(), edge);
farNode = results.get(iterVert.getName());
// Compare the value of the opposite side of the edge, if
// other node is not known.
if (!farNode.isKnown()
&& thisNode.getLabel() + ((Double) edge.getData()).intValue()
< farNode.getLabel()) {
// This path is better, record it.
farNode.setLabel(thisNode.getLabel()
+ ((Double) edge.getData()).intValue());
farNode.setPreviousVertex(thisNode.getCurrentVertex());
// Fix the heap.
heap.percolateUp(farNode.getHeapLocation());
}
}
}
return results;
}