**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 edgeswhileS is non-emptydoremove a node n from S add n totailof Lfor eachnode m with an edgeefrom n to mdoremove edge e from the graphifm has no other incoming edgestheninsert m into Sifgraph has edgesthenreturn error (graph has at least one cycle)elsereturn 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 nodeshttp://www.geeksforgeeks.org/topological-sorting/whilethere are unmarked nodesdoselect an unmarked node n visit(n)functionvisit(node n)ifn has a temporary markthenstop (not a DAG)ifn is not marked (i.e. has not been visited yet)thenmark n temporarilyfor eachnode m with an edge from n to mdovisit(m) mark n permanently unmark n temporarily add n toheadof L

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.

- Choose an arbitrary vertex
- 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.

- Pop the top vertex

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

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 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.

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

Time:O(V+E)

For a general weighted graph, we can calculate single source shortest distances in

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)

functionBellmanFord(listvertices,listedges,vertexsource) ::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 graphfor eachvertex vinvertices:ifvissourcethenweight[v] := 0elseweight[v] :=infinitypredecessor[v] :=null// Step 2: relax edges repeatedlyforifrom1tosize(vertices)-1:for eachedge (u, v)withweight winedges:ifweight[u] + w < weight[v]: weight[v] := weight[u] + w predecessor[v] := u// Step 3: check for negative-weight cyclesfor eachedge (u, v)withweight winedges:ifweight[u] + w < weight[v]:error"Graph contains a negative-weight cycle"returnweight[], 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 Queue**Dijkstra'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.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

**(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)

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**

letdist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)letnext be a |V| × |V| array of vertex indices initialized tonullprocedureFloydWarshallWithPathReconstruction()for eachedge (u,v) dist[u][v] ← w(u,v)// the weight of the edge (u,v)next[u][v] ← vforkfrom1to|V|// standard Floyd-Warshall implementationforifrom1to|V|forjfrom1to|V|ifdist[i][k] + dist[k][j] < dist[i][j]thendist[i][j] ← dist[i][k] + dist[k][j] next[i][j] ← next[i][k]procedurePath(u, v)ifnext[u][v] = nullthenreturn[] path = [u]while u ≠ vu ← next[u][v] path.append(u)returnpath

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- for all edges
- While there is a path from to in , such that for all edges :
- Find
- For each edge
- (
*Send flow along the path*) - (
*The flow might be "returned" later*)

- (

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