Classical Graph Algorithm

Topological Sorting

First, find a list of "start nodes" which have no incoming edges and insert them into a set S; at least one such node must exist in an acyclic graph. Then:

L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges
while S is non-empty do
    remove a node n from S
    add n to tail of L
    for each node m with an edge e from n to m do
        remove edge e from the graph
        if m has no other incoming edges then
            insert m into S
if graph has edges then
    return error (graph has at least one cycle)
else 
    return L (a topologically sorted order)

Modified DFS

An alternative algorithm for topological sorting is based on depth-first search. The algorithm loops through each node of the graph, in an arbitrary order, initiating a depth-first search that terminates when it hits any node that has already been visited since the beginning of the topological sort:

L ← Empty list that will contain the sorted nodes
while there are unmarked nodes do
    select an unmarked node n
    visit(n) 
function visit(node n)
    if n has a temporary mark then stop (not a DAG)
    if n is not marked (i.e. has not been visited yet) then
        mark n temporarily
        for each node m with an edge from n to m do
            visit(m)
        mark n permanently
        unmark n temporarily
        add n to head of L

http://www.geeksforgeeks.org/topological-sorting/
Java Code: https://sites.google.com/site/indy256/algo/topological_sorting

Minimum Spanning Tree Algorithm
Kruskal's algorithm: (Greedy Algorithm + Union-Find)
    sort the edges of G in increasing order by length
    keep a subgraph S of G, initially empty
    for each edge e in sorted order
        if the endpoints of e are disconnected in S
        add e to S
    return S
Note that, whenever you add an edge (u,v), it's always the smallest connecting the part of S reachable from u with the rest of G, so by the lemma it must be part of the MST.

http://www.geeksforgeeks.org/greedy-algorithms-set-2-kruskals-minimum-spanning-tree-mst/
1. Sort all the edges in non-decreasing order of their weight.
2. Pick the smallest edge. Check if it forms a cycle with the spanning tree 
formed so far. If cycle is not formed, include this edge. Else, discard it.  
3. Repeat step#2 until there are (V-1) edges in the spanning tree.
The step#2 uses Union-Find algorithm to detect cycle. 
Java code - Kruskal's Algorithm

private  void KruskalMST()
 {
  // sort the edge list
  Collections.sort(mEdgeList);
  
  UnionFind uf=new UnionFind(mNumVertices);
  
  // Iterating over the sorted input edgeList
  for(int i=0;i<mNumVertices;i++)
  {
   Edge edge=mEdgeList.get(i);
   int v1 = uf.Find(edge.src);  //parent vertex for source
         int v2 = uf.Find(edge.dest); //parent vertex for destinition
         
         
         // if parents do not match, consider edge list for MST and , union the two vertex
         if(v1!=v2)
         {
          mResultantEdgeList.add(edge);
          uf.Union(v1, v2);
         }
  }
  // print the final MST
  printKruskalEdges();
 }

Prim's algorithm
Rather than build a subgraph one edge at a time, Prim's algorithm builds a tree one vertex at a time.
    Prim's algorithm:
    let T be a single vertex x
    while (T has fewer than n vertices)
    {
        find the smallest edge connecting T to G-T
        add it to T
    }
Since each edge added is the smallest connecting T to G-T, the lemma we proved shows that we only add edges that should be part of the MST.

http://www.geeksforgeeks.org/greedy-algorithms-set-5-prims-minimum-spanning-tree-mst-2/
1) Create a set mstSet that keeps track of vertices already included in MST.
2) Assign a key value to all vertices in the input graph. Initialize all key values as INFINITE. Assign key value as 0 for the first vertex so that it is picked first.
3) While mstSet doesn’t include all vertices
….a) Pick a vertex u which is not there in mstSet and has minimum key value.
….b) Include u to mstSet.
….c) Update key value of all adjacent vertices of u. To update the key values, iterate through all adjacent vertices. For every adjacent vertex v, if weight of edge u-v is less than the previous key value of v, update the key value as weight of u-v

void primMST(int graph[V][V])

{

     int parent[V]; // Array to store constructed MST

     int key[V];   // Key values used to pick minimum weight edge in cut

     bool mstSet[V];  // To represent set of vertices not yet included in MST

     // Initialize all keys as INFINITE

     for (int i = 0; i < V; i++)

        key[i] = INT_MAX, mstSet[i] = false;

     // Always include first 1st vertex in MST.

     key[0] = 0;     // Make key 0 so that this vertex is picked as first vertex

     parent[0] = -1; // First node is always root of MST

     // The MST will have V vertices

     for (int count = 0; count < V-1; count++)

     {

        // Pick thd minimum key vertex from the set of vertices

        // not yet included in MST

        int u = minKey(key, mstSet);

        // Add the picked vertex to the MST Set

        mstSet[u] = true;

        // Update key value and parent index of the adjacent vertices of

        // the picked vertex. Consider only those vertices which are not yet

        // included in MST

        for (int v = 0; v < V; v++)

           // graph[u][v] is non zero only for adjacent vertices of m

           // mstSet[v] is false for vertices not yet included in MST

           // Update the key only if graph[u][v] is smaller than key[v]

          if (graph[u][v] && mstSet[v] == false && graph[u][v] <  key[v])

             parent[v]  = u, key[v] = graph[u][v];

     }

}

Strongly Connected Components

• Let G be a directed graph and S be an empty stack.
• While S does not contain all vertices:
  • Choose an arbitrary vertex v not in S. Perform a depth-first search starting at v. Each time that depth-first search finishes expanding a vertex u, push u onto S.
• Reverse the directions of all arcs to obtain the transpose graph.
• While S is nonempty:
  • Pop the top vertex v from S. Perform a depth-first search starting at v in the transpose graph. The set of visited vertices will give the strongly connected component containing v; record this and remove all these vertices from the graph G and the stack S. Equivalently, breadth-first search (BFS) can be used instead of depth-first search.

References:
http://scienceblogs.com/goodmath/2007/10/30/computing-strongly-connected-c/
http://www.acmerblog.com/strongly-connected-components-6099.html
Java code: http://www.sanfoundry.com/java-program-kosaraju-algorithm/

Single-Source Shortest Paths
Bellman–Ford algorithm
It is slower than Dijkstra's algorithm for the same problem, but more versatile, as it is capable of handling graphs in which some of the edge weights are negative numbers

Time:  , where  and  are the number of vertices and edges

function BellmanFord(list vertices, list edges, vertex source)
   ::weight[],predecessor[]

   // This implementation takes in a graph, represented as
   // lists of vertices and edges, and fills two arrays
   // (weight and predecessor) with shortest-path
   // (less cost/weight/metric) information

   // Step 1: initialize graph
   for each vertex v in vertices:
       if v is source then weight[v] := 0
       else weight[v] := infinity
       predecessor[v] := null

   // Step 2: relax edges repeatedly
   for i from 1 to size(vertices)-1:
       for each edge (u, v) with weight w in edges:
           if weight[u] + w < weight[v]:
               weight[v] := weight[u] + w
               predecessor[v] := u

   // Step 3: check for negative-weight cycles
   for each edge (u, v) with weight w in edges:
       if weight[u] + w < weight[v]:
           error "Graph contains a negative-weight cycle"
   return weight[], predecessor[]

Java Code http://www.geekviewpoint.com/java/graph/bellman_ford_shortest_path
http://www.keithschwarz.com/interesting/code/bellman-ford/BellmanFord.java.html

Dijkstra’s shortest path algorithm - Priority QueueDijkstra's algorithm is an asymptotically the fastest known single-source shortest-path algorithm that solves the single-source shortest path problem for a graph with non-negative edge path costs, producing a shortest path tree.

Dijkstra’s algorithm is very similar to Prim’s algorithm for minimum spanning tree. Like Prim’s MST, we generate a SPT (shortest path tree) with given source as root. We maintain two sets, one set contains vertices included in shortest path tree, other set includes vertices not yet included in shortest path tree. At every step of the algorithm, we find a vertex which is in the other set (set of not yet included) and has minimum distance from source.

1) Create a set sptSet (shortest path tree set) that keeps track of vertices included in shortest path tree, i.e., whose minimum distance from source is calculated and finalized. Initially, this set is empty.
2) Assign a distance value to all vertices in the input graph. Initialize all distance values as INFINITE. Assign distance value as 0 for the source vertex so that it is picked first.
3) While sptSet doesn’t include all vertices
….a) Pick a vertex u which is not there in sptSetand has minimum distance value.
….b) Include u to sptSet.
….c) Update distance value of all adjacent vertices of u. To update the distance values, iterate through all adjacent vertices. For every adjacent vertex v, if sum of distance value of u (from source) and weight of edge u-v, is less than the distance value of v, then update the distance value of v.Java Code
http://cs.fit.edu/~ryan/java/programs/graph/Dijkstra-java.html
http://www.algolist.com/code/java/Dijkstra%27s_algorithm
public static void computePaths(Vertex source) { source.minDistance = 0.; PriorityQueue vertexQueue = new PriorityQueue(); vertexQueue.add(source); while (!vertexQueue.isEmpty()) { Vertex u = vertexQueue.poll(); // Visit each edge exiting u for (Edge e : u.adjacencies) { Vertex v = e.target; double weight = e.weight; double distanceThroughU = u.minDistance + weight; if (distanceThroughU < v.minDistance) { vertexQueue.remove(v); v.minDistance = distanceThroughU ; v.previous = u; vertexQueue.add(v); } } } }

(DAG)Shortest Path in Directed Acyclic Graph
Time:O(V+E)
For a general weighted graph, we can calculate single source shortest distances in O(VE) time using Bellman–Ford Algorithm. For a graph with no negative weights, we can do better and calculate single source shortest distances in O(E + VLogV) time using Dijkstra’s algorithm.

Can we do even better for Directed Acyclic Graph (DAG)? We can calculate single source shortest distances in O(V+E) time for DAGs. The idea is to use Topological Sorting.
1) Initialize dist[] = {INF, INF, ….} and dist[s] = 0 where s is the source vertex.
2) Create a toplogical order of all vertices.
3) Do following for every vertex u in topological order.
………..Do following for every adjacent vertex v of u
………………if (dist[v] > dist[u] + weight(u, v))
………………………dist[v] = dist[u] + weight(u, v)



All-Pairs Shortest Paths(APSP) 

1. All-Pairs shortest paths via fast matrix multiplication - O(N^3logN)

Floyd–Warshall algorithm - No negative cycles

Dynamic Programming

Consider a graph G with vertices V numbered 1 through N. Further consider a function shortestPath(i, j, k) that returns the shortest possible path from i to j using vertices only from the set {1,2,...,k} as intermediate points along the way. Now, given this function, our goal is to find the shortest path from each i to each j using only vertices 1 to k + 1.

For each of these pairs of vertices, the true shortest path could be either (1) a path that only uses vertices in the set {1, ..., k} or (2) a path that goes from i to k + 1 and then from k + 1 to j. We know that the best path from i to j that only uses vertices 1 through k is defined by shortestPath(i, j, k), and it is clear that if there were a better path from i to k + 1 to j, then the length of this path would be the concatenation of the shortest path from i to k + 1 (using vertices in {1, ..., k}) and the shortest path from k + 1 to j (also using vertices in {1, ..., k}).

If  is the weight of the edge between vertices i and j, we can define shortestPath(i, j, k + 1) in terms of the following recursive formula: the base case is

and the recursive case is

Path reconstruction

let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
let next be a |V| × |V| array of vertex indices initialized to null

procedure FloydWarshallWithPathReconstruction ()
   for each edge (u,v)
      dist[u][v] ← w(u,v)  // the weight of the edge (u,v)
      next[u][v] ← v
   for k from 1 to |V| // standard Floyd-Warshall implementation
      for i from 1 to |V|
         for j from 1 to |V|
            if dist[i][k] + dist[k][j] < dist[i][j] then
               dist[i][j] ← dist[i][k] + dist[k][j]
               next[i][j] ← next[i][k]

procedure Path(u, v)
   if next[u][v] = null then
       return []
   path = [u]
   while u ≠ v
       u ← next[u][v]
       path.append(u)
   return path

Dynamic Programming | Set 16 (Floyd Warshall Algorithm) - GeeksforGeeksJava
http://cs.anu.edu.au/people/Alistair.Rendell/Teaching/apac_comp3600/module4/all_pairs_shortest_paths.xhtml
code: http://algs4.cs.princeton.edu/44sp/FloydWarshall.java.html

Maximum Flow
Ford Fulkerson Method

Algorithm Ford–Fulkerson

Inputs Given a Network  with flow capacity , a source node , and a sink node 

Output Compute a flow  from  to  of maximum value

1.  for all edges 
2. While there is a path  from  to  in , such that  for all edges :
   1. Find 
   2. For each edge 
      1.  (Send flow along the path)
      2.  (The flow might be "returned" later)

http://blog.csdn.net/smartxxyx/article/details/9293665
Code: http://chuanwang66.iteye.com/blog/1446977

Edmonds–Karp algorithm
It's an implementation of the Ford–Fulkerson method for computing the maximum flow in a flow network in O(V E2) time. 

The algorithm is identical to the Ford–Fulkerson algorithm except that it uses BFS to find the augmenting path

Java code: http://en.wikibooks.org/wiki/Algorithm_Implementation/Graphs/Maximum_flow/Edmonds-Karp

/**
 * Finds the maximum flow in a flow network.
 * @param E neighbour lists
 * @param C capacity matrix (must be n by n)
 * @param s source
 * @param t sink
 * @return maximum flow
 */
public class EdmondsKarp {
    public static int edmondsKarp(int[][] E, int[][] C, int s, int t) {
        int n = C.length;
        // Residual capacity from u to v is C[u][v] - F[u][v]
        int[][] F = new int[n][n];
        while (true) {
            int[] P = new int[n]; // Parent table
            Arrays.fill(P, -1);
            P[s] = s;
            int[] M = new int[n]; // Capacity of path to node
            M[s] = Integer.MAX_VALUE;
            // BFS queue
            Queue<Integer> Q = new LinkedList<Integer>();
            Q.offer(s);
            LOOP:
            while (!Q.isEmpty()) {
                int u = Q.poll();
                for (int v : E[u]) {
                    // There is available capacity,
                    // and v is not seen before in search
                    if (C[u][v] - F[u][v] > 0 && P[v] == -1) {
                        P[v] = u;
                        M[v] = Math.min(M[u], C[u][v] - F[u][v]);
                        if (v != t)
                            Q.offer(v);
                        else {
                            // Backtrack search, and write flow
                            while (P[v] != v) {
                                u = P[v];
                                F[u][v] += M[t];
                                F[v][u] -= M[t];
                                v = u;
                            }
                            break LOOP;
                        }
                    }
                }
            }
            if (P[t] == -1) { // We did not find a path to t
                int sum = 0;
                for (int x : F[s])
                    sum += x;
                return sum;
            }
        }
    }
}