Hi.
Can anyone share their implementation of Dijkstras algorithm (preferably in Java)? I have an O(MlogM) implementation which is not particularly clean. The main problem is that Java PriorityQueue does not support the decrease-key operation. I get around this restriction by putting multiple 'copies' of the same node into the PriorityQueue.
Thanks for your help! Sorry for the long code.
/**
* This is an O(M*logM) implementation. A node may be added more than once
* to the heap, however, every node may add its neighbours only once. There may
* be 2 nodes in the heap with the same index and distance. Such nodes are compared
* using their time of addition to the heap: the node with larger value of time
* wins.
* The tentative minimum distance to a node is best stored in the V[].dis: there
* may be multiple 'same' nodes in the heap with different values of dis.
* Implementation tested against Floyd Warshall.
*/
class djikstras
{
public Vertex V[];
public int N;
public djikstras(int N)
{
this.N=N;
V=new Vertex[N];
for(int i=0;i<N;i++)
V[i]=new Vertex(i,i);
}
public void addEdge(int u,int v,int w)
{
V[u].adj.add(new Edge(v,w));
V[v].adj.add(new Edge(u,w));
}
public int[] shortestDistance(int s)
{
int distances[]=new int[N];
boolean visited[]=new boolean[N]; //true for nodes already in the closest-distance set
for(int i=0;i<N;i++)
V[i].dis=Integer.MAX_VALUE;
V[s].dis=0;
PriorityQueue<Vertex> Q=new PriorityQueue<Vertex>();
Q.add(V[s]);
while (!Q.isEmpty())
{
Vertex cl=Q.poll(); //closest vertex to frontier
if(visited[cl.index]) //if we've processed this node, ignore
continue;
visited[cl.index]=true; //this vertex is now visited
distances[cl.index]=cl.dis; //so finalise the distance of this vertex
for(Edge e:cl.adj)
{
Vertex v=V[e.v];
int weight=e.w;
int distanceThroughCl=cl.dis+weight;
if(distanceThroughCl<v.dis)
{
v.dis=distanceThroughCl; //this also changes the dis in vertex array V[]
//Now generate a new vertex whose time of addition is 1 larger than v
//This ensures that addToHeap bubbles up v
Vertex addToHeap=new Vertex(v.index,v.timeOfAddition+1);
addToHeap.dis=v.dis;
addToHeap.adj=v.adj;
Q.add(addToHeap); //this adds a fresh copy to the heap.
}
}
}
return distances;
}
class Vertex implements Comparable<Vertex>
{
public LinkedList<Edge> adj;
public int dis=Integer.MAX_VALUE;
public int index; //required to build the min-index array
public int timeOfAddition; //for comparison b/w 2 vertices which have the same index and distance
public Vertex(int index,int timeOfAddition)
{
this.index=index;
this.timeOfAddition=timeOfAddition;
this.adj=new LinkedList<Edge>();
}
public int compareTo(Vertex other)
{
if(dis<other.dis)
return -1;
if(dis==other.dis)
{
if(index<other.index)
return -1;
if(index==other.index)
{
//the vertex with greater time of addition should be allowed
//to move up the heap, so that it can displace other nodes
if(timeOfAddition>other.timeOfAddition)
return -1;
}
}
return 1;
}
}
class Edge
{
public final int v;
public final int w;
public Edge(int v,int w) //constructor
{
this.v=v;
this.w=w;
}
}
}
