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

Bash Shortcuts Quick Reference

Ctrl-a          Move to the start of the line.
Ctrl-e          Move to the end of the line.
Ctrl-b          Move back one character.
Ctrl-f          Move forward one character.
Alt-b           Move back one word.
Alt-f           Move forward one word.
Ctrl-] x        Where x is any character, moves the cursor forward to the next occurance of x.
Alt-Ctrl-] x    Where x is any character, moves the cursor backwards to the previous occurance of x.
Ctrl-u          Delete from the cursor to the beginning of the line.
Ctrl-k          Delete from the cursor to the end of the line.
Ctrl-w          Delete from the cursor to the start of the word.
Esc-Del         Delete previous word (may not work, instead try Esc followed by Backspace)
Ctrl-y          Pastes text from the clipboard.
Ctrl-l          Clear the screen leaving the current line at the top of the screen.
Ctrl-x Ctrl-u   Undo the last changes. Ctrl-_ does the same
Ctrl-_          Undo the last command. Don’t forget – it’s Ctrl-Shift-MINUS, not Ctrl-MINUS.
Alt-r           Undo all changes to the line.
Alt-Ctrl-e      Expand command line.
Ctrl-r          Incremental reverse search of history.
Alt-p           Non-incremental reverse search of history.
!!              Execute last command in history
!abc            Execute last command in history beginning with abc
!abc:p          Print last command in history beginning with abc
!n              Execute nth command in history
!$              Last argument of last command
!^              First argument of last command
^abc^xyz        Replace first occurance of abc with xyz in last command and execute it 

Alt-u/Alt-l/Alt-c Uppercase/lowercase/capitalize from cursor to end of word and move cursor past end of word.

Ctrl-s          Suspend currently running terminal.
Ctrl-q          Unsuspend the terminal suspended by Ctrl-S. You need to be aware of this shortcut because 99% of the time you’ve accidentally pressed Ctrl-S and need to undo its effects.

Ctrl-z          Suspend the currently running process (usually followed by bg to resume it in the background or fg to resume in the foreground).

TAB             Autocomplete. Start typing, then hit TAB. You will either get a list of possible completion values (2 TABs needed) or the only choice will be filled in (only 1 TAB is needed).