Graph Algorithms-Properties, Similarity/Differences

Kruskal:

• Kruskal’s algorithm can also run on the disconnected graphs/ Connected Components
• Kruskal’s algorithm can be applied to the disconnected graphs to construct the minimum cost forest, but not MST because of multiple graphs
• (True/False) — Kruskal’s algorithm is best suited for the dense graphs than the prim’s algorithm | False

Prim’s algorithm outperforms the Kruskal’s algorithm in case of the dense graphs.

• Sorting all edges by their weights takes (O(|E| log |E|) time (done in Kruskal’s Algo) | True

Union Find Data Structure:

• When using union-find data structures, using both path compression and rank-based heuristics is superior to (i.e., faster) to using only one of the two.
• MAKE-SET (x)
  1. x.p = x
  2 x:rank = 0
• UNION (x, y) where x and y are formed by MAKE-SET (x) and MAKE-SET (y) uses LINK operation

LINK ( MAKE-SET (x), MAKE-SET (y))

Prim’s Algorithm:

• (True/False) Prim’s algorithm can also be used for disconnected graphs like Kruskal’s | False

Prim’s algorithm iterates from one node to another, so it can not be applied for disconnected graph.

• Prims runs faster in dense graphs and kruskals runs faster in sparse graphs
• (True/False) Prim’s algorithm is simpler than Kruskal’s algorithm | False

Kruskal’s algorithm is comparatively easier, simpler and faster than prim’s algorithm.

Prim’s vs Kruskal’s:

Similarity:

• Both are used to find minimum spanning trees. Both use specialize data structures for their working

Difference:

• Prims runs faster in dense graphs and kruskals runs faster in sparse graphs.
• Kruskal’s algorithm is comparatively easier and simpler than prim’s algorithm.
• Prim’s uses Priority Queue while Kruskal uses Union Find for efficient implementation

Union-find is used by Kruskal’s as it’s useful for cycle detection.

Single Source Shortest Path

Dijkstra’s Algorithm (Greedy)

• (True/False) Dijkstra’s algorithm will always fail if negative-weight edges are present | False

It may still work for some graphs with negative weights, but there should be no negative weight cycles.

• It’s faster to use heap-based Dijkstra’s algorithm (from each vertex as source) to solve the APSP than to run Floyd-Warshall algorithm once if |E| = O(|V |) i.e. sparse graph, when edge weights are POSITIVE | True
  Dijikstra’s Algorithm is MORE EFFICIENT than Bellmann Ford Algorithm | True

Dijkstra’s Algorithm vs Prim’s

Similarity:

• Both of these algorithms are Greedy algorithms with Same running time i.e O (E log V) for Priority Queue and O (|V|²) for naive implementation.

Differences :

• Dijkstra’s Algorithm is used to find the shortest path from source vertex to other vertices in a Graph.
  It works only on both directed and undirected wieghted graphs.
  vs
  Prim’s: This is used to find the Minimun spanning tree in a Graph
  It works only on weighted undirected graph as MST can only be formed from an undirected graph

Dijkstra’s Algorithm vs Kruskal’s

Similarity:

• Both of these algorithms are Greedy algorithms. Both use special data structures

Differences :

• Dijkstra’s Algorithm is used to find the shortest path from source vertex to other vertices.
• It uses Priorty Queue for its working
  vs
  Kruskal’s: This is used to find the Minimun spanning tree in a Graph
  It uses Union Find for its working

Bellmann Ford (DP)

• Bellmann Ford Algorithm can be applied for Directed and weighted graphs
  How many times the for loop in the Bellmann Ford Algorithm gets executed | |V-1|
• Bellmann Ford algorithm is used to indicate whether the graph has negative weight cycles or not. | True

EASE of working : Bellman Ford < Dijakstra

Dijkstra’s Algorithm (Greedy) vs Bellman-Ford Algorithm (DP) vs Topological Sort in DAGs

Similarity:

• All 3 algorithms determine the shortest path from a source vertex to other vertices.

Differences:

• Dijkstra’s Algorithm is a Greedy Algorithm
• In Dijkstra’s negeative edge weights are not allowed.
• It is faster than Bellman Ford
• It works only on both directed and undirected wieghted graphs.
• Time Complexity : O (E log V) with PQ
  vs
• Bellman-Ford Algorithm is a DP based algorithm
• Bellman-Ford Algorithm is Slower than Dijkstra’s
• Negeative edges are allowed but not negative cycles
• It can be applied ony for directed weighted graphs
• Time Complexity: O (|E|.|V|)
  vs
• Topological Sort in DAGs is Greedy
• It uses DFS to get the shortest path. Bellman ford looks at all possible paths
• It works on Graph that contains negative edge weights like Bellman ford
• Time Complexity: O (|E| + |V|)

Bellman Ford(DP) vs Prim(Greedy)
Similarity:

• Both are graph based algorithms

Differences :

• Prim’s Algorithm : is used for finding Minimum spanning tree
• It is a Greedy based algorithm
• It works on Undirected weighted Graph
  vs
• Bellman Ford : determines the shortest path from source vertex to every other vertex.
• It is a DP based algorithm
• It works on directed weighted Graph

All Pair Shortest Path

Floyd-Warshall:

• Floyd Warshall’s Algorithm can be applied on Directed graphs.
  [ From a given directed graph, an adjacency matrix is framed and then all pair shortest path is computed by the Floyd Warshall Algorithm. ]
• Bottom up procedure (DP (recusion- top down)) is being used to compute the values of the matrix elements dij(k)
• What happens when the value of k is 0 in the Floyd Warshall Algorithm | 0 intermediate vertex => Direct node i to node j

Detecting a negative cycle in a Graph

Bellman Ford:

• If we iterate through all edges one more time after |V|-1 iterations and get a shorter path for any vertex, then there is a negative weight cycle.

Floyd Warshall

• We just have to check the nodes distance from itself. It should be ZERO but if it comes out to be negative, we will detect the required negative cycle
• Floyd Warshall Algorithm based solution works for both connected and disconnected graphs.

Naive DP (O(V⁴)) with Repetition (All Pair Shortest Path Algorithm)

• Time Complexity O(V³ (log V))

Bellman Ford (SSSP) vs Naive DP (APSP)

Similarity:

• Both are DP based algorithms.
• The Naive DP approach has a OPT similar to Bellman-Ford with a slight modification OPTj[x,y] — minimum distance from x to y with at most j edges

Differences :

• Naive DP : is used for APSP
• Running Time: O (V³ log V)
  vs
• Bellman Ford : determines the shortest path from source vertex to every other vertex. (SSSP)
• Running Time: O (V.E)

Single Source Shortest Path (SSSP) vs All Pair Shortest Problem (APSP)

Similarity:

• Both the problems focus on finding the shortest path between set of vertices in a graph

Differences:

• In SSSP, the source vertex is fixed. We find the shortest path from source vertex to every other vertex.
• We use Dijkstra’s Algorithm(Greedy) and Bellman-Ford Algorithm (DP) to find the shortest paths
  vs
  In APSP, we find the shortest path from all vertices to every other vertex.
  We use Floyyed Warshal and Naive DP to find the shortest path.

Floyd Warshall

• Floyd Warshal is DP based.
• It doesn’t work only on undirected weighted graphs
• Floyd-Warshall Algorithm is more efficient than running Dijkstra on each vertex in a dense graph
• Floyd-Warshall supports negative weights
• Time Complexity of Floyd-Warshall i.e. O(V³) is less than running Dijkstra on each vertex O(|V||E| + n 2 log n)

Floyyed Warshal vs Naive DP with Exponentition (APSP)

Similarity:

• Both the algorithms determine the shortest path from each vertex to every other vertex. (APSP)

Differences:

Floyyed Warshal: It works on each vertex each time
vs
Naive DP with Exponentition (SSSP) is faster than Floyyed Warshall
It focuses on some vertices with repeated exponentiation

Floyd Warshal (APSP — DP) vs Dijkstra’s Algorithm(SSSP — Greedy)

Similarity

• Dijkstra’s Algorithm can be run on each vertex to give a similar output as Floyd Warshal. Both works on directed weighted graphs.

Differences:

• Dijkstra’s is greedy algo
• It is used for SSSP
• Negative weights not allowed
• Dijkstra can also work on unidirected weighted graphs
• Floyd-Warshall Algorithm is more efficient than running Dijkstra on each vertex in a dense graph
• It’s faster to use heap-based Dijkstra’s algorithm (from each vertex as source) to solve the APSP than to run Floyd-Warshall algorithm once if |E| = O(|V |) / sparse graph, when edge weights are positive.

Residual Network:

Augmenting path

• An s-t path in Gf (not G) consisting of edges with Cf (Residual Capacity ) (e) > 0.
• Reversed Edges are used to find mistakes in the graph

Flow Network / Max Flow (MF) / GRID NETWORK
(True/False) The residual network in a flow network structurally remains constant after every iteration | False

Edge directions of critical edge may change with every interation in a Residual Network (Gf)

• Residual capacity (cf) / Capacity of Flow in Residual Network from vertex v1 to vertex v2 is always greater than 0 | False
  => If v1 and v2 doesn’t have any flow between them, then Residual capacity from v1 to v2 is ZERO
• A flow network on a grid network consisting of m rows and n columns can have largest possible max-flow |f∗| of m+n
• Max s-t cuts = : (n ^ 2) — 2 [total nodes without s and t]
  (either in s or t) 2

(Max Flow) MF => FF (Ford Fulkerson’s method)

Edmond Karp (Max flow)

• Edmond Karp: is a special type of Ford Fulkerson’s method implementaion that converts its psedupolynomial running time to polynomial time.

Ford Fulkerson’s method vs Edmond Karp (Max flow)

Similarity:

• Both the algorithms focus on finding the max flow in a flow network

Differences:

• Ford Fulkerson’s method: Determines the max flow by traversing all the edges
• Time Complexity: O(|E| |f*|) where f* => the number of iterations
• Pseudopolynomial runtime
  vs
• Edmond Karp: is a special type of Ford Fulkerson’s method implementaion that converts its psedupolynomial running time to polynomial time.
  It uses BFS to determine the max flow through s-t path with LEAST number of EDGES
  Time Complexity: O(|V | • |E|²)
  Polynomial runtime

s-t cut vs Proper cut

Similarity:

• Both the algorithms creates partition of the vertices in a graph, resulting into two disjoint subsets.

Differences:

• Proper cut : Used in Prim’s algorithm
• Here, one cut repsents all the vertices along 1 set A, while others represents all vertices in set without A i.e. V/A
  vs
• s-t cut : Used in Max Flow-Min cut theorem
• In a flow network, an s–t cut is a cut that requires the source and the sink to be in different subsets, and its cut-set only consists of edges going from the source’s side to the sink’s side

Max Flow - Min cut Theorm

• The max-flow min-cut theorem states that in a flow network, the maximum amount of flow passing from the source to the sink is equal to the total weight of the edges in the minimum cut, i.e. the smallest total weight of the edges which if removed would disconnect the source from the sink.
• Flow |f1| < c(S, T ) < |f2| | False
  => A flow can never exceed the capacity

Max Flow vs Min cut

Similarity

• Both concepts are defined in flow network

Differences:

• Max-flow refers to a max-value flow in a flow network
  min-cut refers to a min-capacity cut.