PeterGriffin's blog

By PeterGriffin, 11 years ago, In English

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;
			}
		}
	}

Full text and comments »

  • Vote: I like it
  • -3
  • Vote: I do not like it

By PeterGriffin, 12 years ago, In English

Hi all!

I have seen the 2-Pointers method being used in some problems. For example, it was used in the recent Codeforces contest in problem D: http://www.codeforces.com/contest/190/problem/D. I found the solution very interesting.

Also, in my TopCoder post http://apps.topcoder.com/forums/?module=Thread&threadID=733641&start=0&mc=6#1480079, AzizKhan gave a very nice solution using 2 pointers.

Can someone point me to more similar problems so that I can practice this approach? Thanks in advance!

Full text and comments »

  • Vote: I like it
  • -5
  • Vote: I do not like it