PeterGriffin's blog

By PeterGriffin, 9 years ago, In English


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)
		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++)

		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
			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;
					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);
					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.adj=new LinkedList<Edge>();

		public int compareTo(Vertex other)
				return -1;
					return -1;
					//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
  • Vote: I like it
  • -3
  • Vote: I do not like it