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