GATE 2022: Study Notes on Shortest Paths

By Mallesham Devasane|Updated : December 12th, 2021

Graph: nodes/vertices, and edges/arcs as pairs of nodes.

Directed graph: edges are ordered pairs of nodes.

Weighted graph: each edge (directed/undirected) has a weight.

The path between a pair of nodes vi, vk: sequence of edges with vi, vk at the two ends.

Simple path: covers no node in it twice.

Loop: a path with the same start and end node.

Path length: number of edges in it.

Path weight: total wt of all edges in it.


Connected graph: there exists a path between every pair of nodes, no node is disconnected.

Complete graph: edge between every pair of nodes

Acyclic graph: a graph with no cycles.

Topological Sort: In directed acyclic graph, sequentially order the nodes without violating any arc ordering. Such order is topological sort or topological order.

Biconnected graph: undirected connected graph where removal of no vertex disconnects the rest of the graph.

Articulation points: vertex like the ones mentioned above. So, bi-connected graphs are graphs without articulation points.

Strongly-connected component: a subgraph in which there is a path between every pair of nodes

Note: The whole graph could be strongly connected. Only a single node could form its own SCC.

  • The whole graph could be strongly connected.
  • Only a single node could form its own SCC.

SCC creates partition of nodes in a graph: every node is in a SCC, & no node is outside all SCC’s.

A sub-graph of a SCC could be an SCC itself, although not necessarily.

Each Spanning Tree of a graph is a strongly connected component of G.

For every pair of nodes (v, w) in any Spanning Tree of a graph there exists a path v->w and a path w->v.

Every spanning tree is a sub-tree of a spanning tree of a graph.

Clique: In graph theory, a clique in an undirected graph is a subset of its vertices such that every two vertices in the subset are connected by an edge. A maximal clique is the largest clique containing a given node.

Graph Algorithms:

  • Graph traversal with visitor support: BFS, DFS
  • Cycle detection
  • Connected components
  • Topological sorting
  • Shortest paths: Dijkstra, Floyd-Warshall, A*
  • Minimum spanning trees: Prim, Kruskal
  • Flow: Minimum Cut
  • Random graph generation


Single Source Shortest Paths

Shortest path problem is to determine one or more shortest path between a source vertex s and a target vertex t, where a set of edges are given.

Consider a directed graph G = (V, E) with non-negative edge weight and a distinguished source vertex, s ∈ V. The problem is to determine the distance from the source vertex to every other vertex in the graph. 

Dijkstra's Algorithm
  • Dijksta's algorithm solves the single source shortest path problem on a weighted directed graph.
  • It is Greedy algorithm.
  • Dijkstra's algorithm starts at the source vertex, it grows a tree T, that spans all vertices reachable from S.
  • Dijkstra's algorithm works similar to Prim's algorithm.
  • It uses BFS (Breadth First Search) to find the shortest distances.
  • The following simple algorithm explains the working principle of Dijkstra's algorithm.
  Dijkstra's Algorithm Implementation using Heap:
Analysis of Dijkstra's Algorithm: Time complexity is similar to Prim's algorithm
  • Using Heap : Time complexity is O( |E| log |V| )
  • Using Fibonacci Heap : Time complexity is O(|E| + |V| log |V| )
  • Using Adjacency list : Time complexity is O(|V|2)
Note: Dijkstra's algorithm does not work with negative edge weights. It is important to know that Dijkstra's algorithm requires that weights of all edges are non-negative. Otherwise the procedure is not able to determine whether the shortest path for the node was already found or not.
Let A be the starting (source) vertex in the above graph. Then shortest distance from A will be selected as 2. If we want to find shortest distance from A to B, it will result 2 using Dijkstra's algorithm. But actual shortest distance is 1 if we choose A to C to B path.
Bellman Ford Algorithm
  • Bellman-Ford algorithm solves the single-source shortest-path problem in the general case in which edges of a given digraph can have negative weight as long as given graph G contains no negative cycles.
  • Bellman Ford not uses Greedy approach to find the shortest paths.
  • The algorithm requires that the graph does not contain any cycles of negative length, but if it does, the algorithm is able to detect it.
Pseudo Code for Bellman Ford:
Analysis of Bellman Ford Algorithm:
We assume that the algorithm is run on a graph G with |V| nodes  and  edges. Let |V|=n, and |E|=m.
  1. At the beginning, the value ∞ is assigned to each node.This requires O(n)
  2. Then we do the phases of the algorithm: one phase less than the number of nodes. In each phase, all edges of the graph are checked, and the distance value of the target node may be changed. We can interpret this check and assignment of a new value as one step and therefore have steps in each phase. In total all phases together require steps. This requires O(mn)
  3. Afterwards, the algorithm checks whether there is a negative circle, for which he looks at each edge once. Altogether he needs  steps for the check. O(m)

Total Time complexity for Bellman Ford Algorithm: O(m n) = O(|E|.|V|)

Floyd - Warshall Algorithm
  • It can find shortest (longest) paths among all pairs of nodes in a graph, which does not contain any cycles of negative length.
  • It is dynamic programming algorithm.
  • It can be used to detect the presence of negative cycles.
  • It can find transitive closure for directed graph.
Pseudo Code for Floyd-warshall algorithm: Let n be the number of vertices in the graph G.
  • Pred [x,y] can be used to store the reachability and will help to extract the final path between two vertices.
  • d[n,n] will store the result for all pairs shortest paths.
  • w[i, j] contains the weight of an edge (i, j) for the given graph G.

Analysis of Floyd - Warshall Algorithm:

  1. In the beginning of code there are two loops, which requires O(n2) time and two statements inside the inner loop takes constant time.
  2. Next, there are three loops. These three loops can require O(n3) time. If statement of the inner loop requires constant time.

Time complexity of Floyd - Warshall Algorithm = O( n)




write a comment

Follow us for latest updates