Dijkstra’s shortest-path

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;

/* Dijkstra’s shortest-path */

public class ShortestPath {
	static int[][] g1 = 
	{ // head,tail,weight
		{0,1,41},
		{1,2,51},
		{2,3,50},
		{4,3,36},
		{3,5,38},
		{3,0,45},
		{0,5,29},
		{5,4,21},
		{1,4,32},
		{4,2,32},
		{5,1,29}
	};

	static int[][] g2 = 
	{ // head,tail,weight
		{0,1,2},
		{0,2,3},
		{1,3,3},
		{1,4,1},
		{2,3,1},
		{2,4,1},
		{3,5,2},
		{4,5,3}
	};
	
	public static void main(String[] args) {
		Graph<Integer> G = new Graph<Integer>();
		
		
		for(int[] e : g1){
			Edge<Integer> edge = new Edge<Integer>(e[0],e[1],e[2]);
			G.add(edge);
		}
		
		ShortestPath sp = new ShortestPath();
		int[] start = {0,5,3};
		for(int s : start){
			System.out.println("\n=========starts from " + s);
			List<Edge<Integer>> spt = sp.dijkstra(G, s);
			for( Edge<?> e : spt)System.out.printf("(%s,%s) ", e.head(),e.tail());
		}
	}
	
	//=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+
	<T> List<Edge<T>> dijkstra(Graph<T> G, T s /* start from here */) 
	{
		Map<T, Object> found = new HashMap<T, Object>(); // vertices already included in shortest path
		List<Edge<T>> spt = new ArrayList<Edge<T>>(); // shortest path
		
		PriorityQueue<Edge<T>> pq = new PriorityQueue<Edge<T>>(100, Edge.BY_WEIGHT_FROM_SOURCE);
		for (Edge<T> e : G.adj(s)){
			e.weight_from_source = e.weight();
			pq.offer(e);
		}

		while (!pq.isEmpty()) {
			Edge<T> cheapest_from_s = pq.poll(); // cheapest edge from s (includes edges of path more then 1)

			// if we already know a cheap path from s to cheapest_from_s.tail continue.
			// we could have removed all the paths from s to  cheapest_from_s.tail
			// when we found the cheapest path, but we waited till it popped out from queue.
			if (found.containsKey(cheapest_from_s.tail()))
				continue; 
			
			if(s.equals(cheapest_from_s.tail())) // came back to start, all other vertices might not have visited
				continue;
			
			found.put(cheapest_from_s.tail(), null);
			
			spt.add(cheapest_from_s);
			
			for (Edge<T> a : G.adj(cheapest_from_s.tail())) {
				a.weight_from_source = cheapest_from_s.weight_from_source + a.weight();
				pq.offer(a);
			}
		}
		
		return spt;
	}
	//=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+
}

class Graph<T> {
	
	/* adjacency list */
	private Map<T, List<Edge<T>>> adjlist = new HashMap<T, List<Edge<T>>>();
	
	/* total number of edges */
	private int nedges=0;
	
	/*add new edge to graph*/
	void add(Edge<T> e) { 
		List<Edge<T>> adj = adjlist.get(e.head());
		if (adj == null) {
			adj = new ArrayList<Edge<T>>();
			adjlist.put(e.head(), adj);
		}
		adj.add(e);
		nedges++;
	}
	
	/*returns edges adjacent to v*/
	List<Edge<T>> adj(T v){ return adjlist.get(v);}
	
	/*returns number of vertices in the graph*/
	int nvertices(){ return adjlist.size();}
	
	/*returns number of edges in the graph*/
	int nedges(){ return nedges;}
}

class Edge<T> {
	private T head, tail;
	private int weight;
	
	int weight_from_source = Integer.MAX_VALUE; // unknown

	Edge(T head, T tail, int weight) {
		this.head = head;
		this.tail = tail;
		this.weight = weight;
	}

	T       head  ()    {return head;}
	T       tail  ()    {return tail;}
	int     weight()    {return weight;}
	boolean from  (T v) {return head.equals(v);}
	
	public String toString() {
		return String.format("(%s,%s/%d-%d)",head,tail,weight,weight_from_source);
	}

	public static final 
	Comparator<Edge<?>> BY_WEIGHT_FROM_SOURCE = new Comparator<Edge<?>>() {
		public int compare(Edge<?> e1, Edge<?> e2) {
			if (e1.weight_from_source < e2.weight_from_source)
				return -1;
			if (e1.weight_from_source == e2.weight_from_source)
				return 0;
			return 1;
		}
	};
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s