Other Algo’s & concepts

Floyd Warshall (DP)

Floyd-Warshall Algorithm is an algorithm for finding the shortest path between all the pairs of vertices in a weighted graph. This algorithm works for both the directed and undirected weighted graphs. But, it does not work for the graphs with negative cycles (where the sum of the edges in a cycle is negative)

Note : Djikstra finds shortest dist from a single source so we can use Djikstra on every vertex ( O(N²) * O(N) = O(N³)

Algo :

• Create a matrix A0 of dimension n*n where n is the number of vertices. The row and the column are indexed as i and j respectively. i and j are the vertices of the graph.
• Each cell A[i][j] is filled with the distance from the ith vertex to the jth vertex. If there is no path from ith vertex to jth vertex, the cell is left as infinity.

Usually this A⁰ matrix is given to us in the input

• Now, create a matrix A1 using matrix A0. The elements in the first column and the first row are left as they are. The remaining cells are filled in the following way.
• Let k be the intermediate vertex in the shortest path from source to destination. In this step, k is the first vertex. A[i][j] is filled with :

(A[i][k] + A[k][j]) if (A[i][k] + A[k][j] < A[i][j])

• That is, if the path through the vertex k is shorter than the direct distance from the source to the destination , then the cell is filled with A[i][k] + A[k][j].
• In this step, k is vertex 1. We calculate the distance from source vertex to destination vertex through this vertex k

• Similarly, A2 is created using A1. The elements in the second column and the second row are left as they are. In this step, k is the second vertex (i.e. vertex 2). The remaining steps are the same as in step 2.

• Similarly, A3 and A4 is also created

Code : O(V³ ) time & O(V²) space

#define INF 10000
void floydWarshall(int graph[][V])  
{
int dist[V][V], i, j, k;
for (i = 0; i < V; i++) {
for (j = 0; j < V; j++)
dist[i][j] = graph[i][j];
}
// **** ALGO BEGINS ******
for (k = 0; k < V; k++) { // 0 based index that's why k is from 0
                         // Pick all vertices as source one by one
  for (i = 0; i < V; i++) {      // source
    for (j = 0; j < V; j++) {   // destination
      if (dist[i][k] + dist[k][j] < (dist[i][j]) 
      dist[i][j] =   dist[i][k] + dist[k][j];
      }
    }
  }
}
int main() {
  int graph[4][4] = {{0, 3, INF, 5},
             {2, 0, INF, 4},
             {INF, 1, 0, INF},
             {INF, INF, 2, 0}};
  floydWarshall(graph);
}

Note : We decided a random large value for INF i.e INF=10000 to prevent overflow because of we had selected INF = INT_MAX then

if (dist[i][k] + dist[k][j] would have given overflow

If we wish to take INF=INT_MAX then just check for one more condition

# define INT INT_MAX
if ( dist[i][k] != INF && 
     dist[k][j] != INF && 
     dist[i][k] + dist[k][j] < dist[i][j]
    )

Bellman–Ford Algorithm (DP) for single source shortest path

Note that Dijkstra doesn’t work for Graphs with negative weight edges it may end up in an infinite loop since everytime dist would decrease, so Bellman-Ford works for such graphs. But time complexity of Bellman-Ford is O(VE), which is more than Dijkstra (in the worst case i.e for complete graph we can have — : — V*(V-1) edges so time becomes O(V³ ) — abdul bari

Why would one ever have edges with negative weights in real life?

Negative weight edges might seem useless at first but they can explain a lot of phenomena like cashflow, the heat released/absorbed in a chemical reaction, etc.

For instance, if there are different ways to reach from one chemical A to another chemical B, each method will have sub-reactions involving both heat dissipation and absorption.

If we want to find the set of reactions where minimum energy is required, then we will need to be able to factor in the heat absorption as negative weights and heat dissipation as positive weights.

Caution : Bellman fails for negative cycle

Algo

• This DP algorithm calculates shortest paths in a bottom-up manner.
• It first calculates the shortest distances which have at-most one edge in the path. Then, it calculates the shortest paths with at-most 2 edges, and so on.
• After the i-th iteration of the outer loop, the shortest paths with at most i edges are calculated.
• For V vertices , there can be maximum |V| — 1 edges in any simple path, that is why the outer loop runs |v| — 1 times. The idea is, assuming that there is no negative weight cycle, if we have calculated shortest paths with at most i edges, then an iteration over all edges guarantees to give shortest path with at-most (i+1) edges

If a negative weight cycle exists then after running the outer loop for V-1 times , if we again run it one more time, we’ll get an updated result else if no negative weight cycle exists then no matter how many times we iterate after V-1 times , we’ll definitely get the same result i.e. no dist. would get updated

Therefore a very important application of Bellman Ford is to check if there is a negative cycle in the graph,

Note : This algo works for (directed edges or undirected edges ) with no negative cycle

Every undirected edge can be converted into directed but the only condition is no negative cycle should be there

Summary of the algo :

* So we need to relax all the edges V-1 times, starting from any edge where the relaxation rule is :

* distance[V] < distance[U] + cost(U, V) then only update

Code : time complexity O((V-1)*E)

#include<bits/stdc++.h>
using namespace std;
struct node {
  int u;
  int v;
  int wt;
  node(int first, int second, int weight) {
    u = first;
    v = second;
    wt = weight;
  }
};
int main() {
  int V, E;
  cin >> V >> E;
  vector < node > edges;
  for (int i = 0; i < E; i++) {
    int u, v, wt;
    cin >> u >> v >> wt;
    edges.push_back(node(u, v, wt));
  }
int src;
  cin >> src;
int inf = 10000000;
  vector < int > dist(V, inf);
dist[src] = 0;
for (int i = 1; i <= V - 1; i++) { // V-1 times
    for (auto it: edges) {
      if (dist[it.u] + it.wt < dist[it.v]) {
        dist[it.v] = dist[it.u] + it.wt;
      }
    }
  }
bool NegativeWeightCycle = false;
  for (auto it: edges) {
    if (dist[it.u] + it.wt < dist[it.v]) {
      cout << "Negative Cycle";
      NegativeWeightCycle = 1;
      break;
    }
  }
if (!NegativeWeightCycle) {
    for (int i = 0; i < V; i++) {
      cout << i << " " << dist[i] << endl;
    }
  }
return 0;
}

SUMMARY

• shortest distance from source to all other nodes with negative weights allowed -Bellman Ford O(E.V)
• shortest distance from source to all other nodes with negative weights not allowed -Dijkstra’s Algorithm (E+V).logV
• shortest distance between all pairs of nodes -Floyd-Warshal O(V³)
• shortest dist in DAG (non negative equal edges or no edges) -topological sort using bfs/dfs — O(E+V)

Kosaraju’s Algorithm (For Strongly Connected Components i.e SCC)

A strongly connected component is the portion of a directed graph in which there is a path from each vertex to another vertex. It is applicable only on a directed graph.

Eg let this be the given graph (visit here for detailed explaination)

The strongly connected components of the above graph are:

These components can be found using Kosaraju’s Algorithm

Algo in short :

Do a DFS on the original graph, keeping track of the finish times of each vertex. This can be done with a stack, when some DFS finishes put the source vertex on the stack. This way node with highest finishing time will be on top of the stack.

Reverse directions of all edges to obtain the transposed graph.

Do DFS on the reversed graph, with the vertex on top of the stack and keep marking the vertices visited. When DFS finishes, all vertices visited will form one Strongly Connected Component. If any more vertex remains unvisited, this means there are more Strongly Connected Component’s, so pop vertices from top of the stack until a valid unvisited node is found. This step is repeated until all nodes are visited

Algo in detail

It does modified DFS two times

• Now what elements we get in DFS depends on the vertex we started as source for our dfs call Eg if we start from vertex 0, dfs will print all the vertices of the graph since there are directed edges leading to other vertices but if we start dfs from vertex 7, we only get 7 since there’s no edge coming from vertex…so we need a particular order of vertices
• Best way is to take vertices in the increasing order of their finishing time
• So for the first dfs simply do dfs as usual and when no adjacent vertcices are left to visit then push that vertex into the stack (similar to topological sort using dfs (both are diff topics though)
• After the dfs , we’ll get the vertices in increasing order of their finishing time & the top of the stack contains the max finish time vertex
• Now we transpose the graph i.e if there’s ad edge b/w u → v , we remove it and instead add an edge from v → u & reinitialize the visited array to false
• Now one by one pop a vertex from stack and if that vertex is not visited , do another dfs call for that vertex else we simply pop it and go for next vertex
• The 2nd dfs starting (from the popped vertex which was not visited) will print all the strongly connected components (SCC) of that vertex

Kosaraju’s Algorithm Complexity

Kosaraju’s algorithm runs in linear time i.e. O(V+E).

Code :

void dfs(int start, vector < int > adj[], vector < bool > & visited, stack < int > & st) {
    visited[start] = true;
    for (auto it: adj[start]) {
       if (visited[it] == false)
          dfs(it, adj, visited, st);
    }
    st.push(start);
 }
 void dfs_rev(int start, vector < bool > & visited, vector < int > transpose_adj []) {
    cout << start << " ";
    visited[start] = true;
    for (auto it: transpose_adj[start]) {
       if (visited[it] == false)
          dfs_rev(it, visited, transpose_adj);
    }
 }
 int kosaraju(int V, vector < int > adj[]) {
// **** DFS 1 to store the order in stack
       stack < int > st;
       vector < bool > visited(V, false);
       for (int i = 0; i < V; i++) {
          if (visited[i] == false) {
             dfs(i, adj, visited, st);
          }
       }
// **** TRANSPOSE
       vector < int > transpose_adj[V];
       for (int i = 0; i < V; i++) {
          visited[i] = false;
          for (auto it: adj[i])
             transpose_adj[it].push_back(i);
       }
// **** DFS 2 using the stack
       while (!st.empty()) {
          int node = st.top();
          st.pop();
          if (visited[node] == false) {
             cout << "SCC: ";
             dfs_rev(node, visited, transpose_adj);
             // after this call one complete
             // SCC would have been covered
             cout << endl;
          }
       }
}

Question: Find the no of strongly connected components in a graph (my solution)