### PeterGriffin's blog

By PeterGriffin, 9 years ago, 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)
{
}

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>();

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

{
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
}
}
}
return distances;
}

class Vertex implements Comparable<Vertex>
{
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

{
this.index=index;
}

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
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;
}
}
} java, Comments (0)