Dijkstra

Dijkstra's algorithm is a method to compute the shortest path between two nodes in a graph. One possible use could be for calculating the best driving route in a road network (vertices are intersections and edges weights are the time needed to travel a road).

The basic algorithm requires:

The method of determining priority is by shortest known distance from the initial node. At the start of the algorithm we only know that the initial node is 0 distance away from itself, all other nodes are an initially known to be an infinite distance away. Therefore the first node to come off the queue will be our starting node, at which point we mark it visited and update the shortest paths (and thus the priority queue) to all its neighbors. As each node is visited the known shortest distance to it's neighbor nodes are updated. Since all other paths are larger than the one that comes off the priority queue at each iteration, it is guaranteed that when a node comes of the queue its shortest path is known. This means that when our target node comes off the queue the algorithm is completed.

The complexity of the algorithm depends largely on what data structures are chosen to represent the graph and the priority queue. If the distances are stored in a normal array and a linear search is performed to find the next minimum the complexity is \$O(V^2 + E)\$(see Big O notation). If a binary heap is used for the priority queue the complexity is \$O((E+V)\log(V))\$. A fibonacci heap will improve this to \$O(E + V\log V)\$ as pushing values onto the heap is \$O(1)\$.

Here are a number of implementations of the algorithm. The assumed input format is:
V E
v v w

where V is # of vertices, E is # of edges, followed by E lines where v are vertex numbers and w is the associated edge weight.

```import java.io.*;
import java.util.StringTokenizer;
public class dij
{
static boolean visited[]=new boolean[1000]; // 1000 would be the max number of nodes
static long adj[][]=new long[1000][1000]; // to store the graph in an adjacency matrix (see graph storage)
static long best[]=new long[1000];
public static void main(String[] args) throws Exception
{
PrintWriter out=new PrintWriter(new BufferedWriter(new FileWriter("dij.out")));
int V=Integer.parseInt(token.nextToken()); // Number of vertices
int E=Integer.parseInt(token.nextToken()); // Number of edges
long MAX=555555555; // setting our "infinity" value
for(int i=0; i<V; i++) // Let's set all the entire graph to inf.
for(int j=0; j<V; j++)
for(int i=0; i<E; i++)
{
int v1=Integer.parseInt(token.nextToken())-1;
int v2=Integer.parseInt(token.nextToken())-1;
int len=Integer.parseInt(token.nextToken());
// Let's protect ourselves from overwriting good paths. Example: 1 2 5, then 1 2 7.
// A normal read would overwrite the length 5 with 7, which would not preserve
// the "shortest" path. The statement is also one of those wacked up if-else statements
// that to preserve space, jumbles everything up. It wants to say, if adj[v1][v2]<len, then
}
for(int i=0; i<V; i++)
{
best[i]=MAX; // The 'best' array is the shortest path to the node.
visited[i]=false; // The visited array is pretty self-explanatory
}
best[0]=0; // We are starting at node '0', so the best is 0 (we're already there)
for(int i=0; i<V; i++)
{
long min=MAX;
int curnode=0; // This is our current node
for(int j=0; j<V;j++) //
if(!visited[j]&&best[j]<min)
{
curnode=j;
min=best[j];
}
visited[curnode]=true;
for(int j=0; j<V; j++)