So how exactly does this algorithm work? Basically, we initialize all the distances to infinity, except for the root Vertex which is initialized to 0. We then traverse the Graph from the starting point towards the end point. When we hit a Node, we evaluate the cumulative distance to that Node, which means the distance recorded at the previous Node plus to the distance to the current Node. So if we have A-->B weighted at 5 and B-->C weighted at C, B would record the distance 5, and C would record the distance 8. The reason we initialize to infinity is that the first time we hit that Node, everything will be less than infinity so the first distance will be stored at that Node.
For the purpose of this tutorial, I've set up a class to handle evaluating Dijkstra's algorithm using my Graph implementation from my Graphs Tutorial. I used Integer.MAX_VALUE as my infinity marker.
import java.util.*;
/**
* A utility class to implement Dijkstra's algorithm
* @param E: The type to store in the Graph
* */
public class Dijkstra<E> {
//the Graph to traverse
private Graph<E> graph;
//the PriorityQueue for the heap-based sort
private PriorityQueue<Connector<E>> heap;
/**
* @param graph: The Graph to traverse
*
* The constructor initializes each Node's
* distance to Integer.MAX_VALUE, as the infinity value.
* When the weights are compared, they are initially compared
* to MAX_VALUE, which they will be less than.
* */
public Dijkstra(Graph<E> graph){
this.graph = graph;
resetGraph();
heap = new PriorityQueue<Connector<E>>(25, new Comparator<Connector<E>>(){
public int compare(Connector<E> one, Connector<E> two){
return (one.getDistance() + one.getOne().getDistance()) -
(two.getDistance() + two.getOne().getDistance());
}
});
}
//initializes the Graph Nodes to infinity
public void resetGraph(){
for(int i = 0; i < this.graph.count(); i++){
this.graph.get(i).setDistance(Integer.MAX_VALUE);
}
}
In this implementation of Dijkstra's algorithm, I'm using a naive, unamoritzed implementation. It comes down to basically a recursive depth-first search, updating distances for the Nodes. The minimum distance is found, and returned. Because all paths are evaluated naievely, the runtime of this implementation is O(V2), where v is the number of vertices in the Graph.
/**
* @param start: The Node to start from
* @param end: The target Node
* @param dist: The cumulative distance at this point
*
* This method is implemented recursively, finding the distance of
* the shortest path from some starting Node to the ending Node.
* I utilize Tree-recursion, comparing the results of the child calls
* to get a shortest distance.
* */
public int nonheapPath(Edge<E> start, Edge<E> end, int dist){
LinkedList<Connector<E>> connections = start.getConnections();
//set the weight to a maximum that every other weight has to
//be less than
int weight = Integer.MAX_VALUE;
//if we're at the end Node, stop
if(start == end)
return dist;
//for each child Node from start
for(int i = 0; i < connections.size(); i++){
Connector<E> temp = connections.get(i);
Edge<E> update = temp.getTwo();
//check to see if the new distance is shorter than the current one
if(update.getDistance() > (dist + temp.getDistance())){
//and update it if it is
update.setDistance(dist + temp.getDistance());
}
//now compare the current distance to the rest of the weights returned
//by child calls. Note the depth-first traversal here
weight = Math.min(weight, nonheapPath(update, end, update.getDistance()));
}
return weight;
}
This implementation of Dijkstra's algorithm is optimized and utilizes a greedy approach. The minimal paths are pushed onto a PriorityQueue, giving us a better idea of which path to evaluate next based on which has the lowest cost. We begin at the starting Node, which is initialized to a distance of 0. We then push its children onto the PriorityQueue, and poll the next one to evaluate, utilizing a breadth-first search over a depth-first search. We also do not need to store or evaluate minimum weights as we did in the previous version, as when the PriorityQueue is empty, the Graph will have been fully evaluated, and end will have the shortest distance to it, which we can return. Based on this optimization, the runtime improves from O(V2) to O(E log(V)), where E is the number of Edges (or Connectors) in the Graph.
/***
* @param start: The starting point
* @param end: The ending point
* @return int: The shortest distance from start to end
*
* This method uses a PriorityQueue to determine which Edge
* to visit next. Nodes are evaluated in a breadth-first search,
* and pushed onto the PriorityQueue. The PriorityQueue is then polled
* and the process is repeated until the PriorityQueue is empty.
* */
public int heapPath(Edge<E> start, Edge<E> end){
start.setDistance(0); //initialize the start distance to 0
//the Edge to evaluate. We evaluate the start Node first
Edge<E> evaluate = start;
//as long as we have elements in the Graph to traverse
do{
//push evaluate's children onto the PriorityQueue
LinkedList<Connector<E>> connections = evaluate.getConnections();
Iterator<Connector<E>> iterate = connections.iterator();
while(iterate.hasNext()){
heap.add(iterate.next());
}
//then poll the PriorityQueue to determine
//which Node to visit next
Connector<E> temp = heap.poll();
evaluate = temp.getTwo();
//and update that Node's distance if a shorter path is found
int distance = evaluate.getDistance();
int newDist = temp.getOne().getDistance() + temp.getDistance();
if(newDist < distance)
evaluate.setDistance(newDist);
} while (!heap.isEmpty());
return end.getDistance();
}
If you want a test Graph to set this up with, I have gone ahead and set up the Graph to match the animation on Wikipedia.
/**
* Below, I set up the Graph on Wikipedia: http://en.wikipedia.org/wiki/Dijkstra's_Algorithm
* */
public static void main(String[] args){
Graph<Integer> list = new Graph<Integer>();
Edge<Integer> i = new Edge<Integer>(1, 0);
Edge<Integer> j = new Edge<Integer>(2, 0);
Edge<Integer> k = new Edge<Integer>(3, 0);
Edge<Integer> l = new Edge<Integer>(4, 0);
Edge<Integer> m = new Edge<Integer>(5, 0);
Edge<Integer> n = new Edge<Integer>(6, 0);
list.addEdge(i);
list.addEdge(j);
list.addEdge(k);
list.addEdge(l);
list.addEdge(m);
list.addEdge(n);
i.connectTo(j, 7);
i.connectTo(k, 9);
i.connectTo(n, 14);
j.connectTo(k, 10);
j.connectTo(l, 15);
k.connectTo(n, 2);
k.connectTo(l, 11);
l.connectTo(m, 6);
n.connectTo(m, 9);
Dijkstra<Integer> test = new Dijkstra<Integer>(list);
}
}
MultiQuote
| 