Shortest and Longest Path Algorithms: Job Interview Cheatsheet

Image from Wikipedia

A quick overview and comparison of shortest and longest path algorithms in graphs.

There are so many little points to remember about innocent looking shortest and longest path problems in graphs. Questions on this topic are very common in technical job interviews for computer programmers. However, it is often hard to keep your memory fresh and remember all details about these problems and their algorithms.

For example:

  • Did you know finding the shortest simple path in a graph is NP-hard? (if not, see the section for longest path below)
  • Did you know in some graphs shortest path can be found in linear time?

Here I provide a quick summary and important points about each of the famous algorithms in one place, which can be reviewed quickly before each interview.

Before we begin:

First, we assume the graph is G(V, E) has , where

  • V = {1, 2, … , n} , |V| = n
  • |E| = m

For the shortest path problem, we assume we are after the shortest non-simple path, i.e., vertices can repeat. Also, we assume the edge weights can be an integer value, i.e., positive, negative, or zero.

The Shortest Distance problem only requires the shortest distance between nodes, whereas The Shortest Path Problem requires the actual shortest path between nodes. We discuss the shortest distance problem here. The shortest path can usually be found with minor enhancement in the algorithm.

Floyd-Warshall Algorithm

Floyd-Warshall is the simplest algorithm:

Intuition: We calculate the shortest possible path from node i to j using nodes only from the set {1, 2, …, k} as intermediate points between them. We sweep k from 1 to n, and update d[i][j], the distance between nodes i and j:

d[i][j] = min( d[i][j], d[i][k] + d[k][j] )

Below is the implementation in C++:

What You Need to Know about Floyd-Warshal Algorithm:

  • It finds the shortest distance between all pairs of nodes.
  • It is O(n³)
  • It is a dynamic programming algorithm
  • The graph CAN have negative edges
  • The graph CANNOT have negative cycles

Dijkstra Algorithm

Dijkstra algorithm finds the shortest path between a single source and all other nodes.

Intuition: Keep a list of visited nodes. At each step:

  1. Find the unvisited node u with shortest distance
  2. Relax the distance of neighbors of u
  3. Add u to the visited list and repeat

Below is Dijkstra’s implementation in C++:

What You Need to Know about Dijkstra’s Algorithm:

  • The run-time is: O(n²) simple form. With min-heap: O( (m+n)log(n) ). With Fibonacci heap: O(m+n log n)
  • It’s a greedy algorithm
  • It CANNOT handle negative edges or negative cycles

Below is Dijkstra’s algorithm using a priority queue in C++:

Bellman-Ford Algorithm

This algorithm finds shortest distance from source to all other nodes.

Intuition: We have two loops:

  • The inner loop: We iterate on all edges. At each iteration we relax the distances by using edges from 0 to j.
  • The outer loop: We repeat the inner loop n-1 times

Bellman-Ford Algorithm. Picture taken from here.

After the i-th iteration of the outer loop, the shortest paths with at most i edges are calculated. There can be maximum n – 1 edges in any simple path, so we repeat n – 1 times.

Below is an implementation of Bellman-Ford algorithm in C++.

Bellman-Ford Algorithm. Notice that we use an adjacency matrix to iterate edges

What you need to know about Bellman-Ford Algorithm

  • Run Time: O(m.n).
  • If we use the adjacency matrix (as in the above code) to iterate edges, the run time is O(n³)
  • It CAN handle negative edges
  • It CAN report negative cycles

Shortest Distance in DAGs

Shortest distance in a DAG (Directed Acyclic Graph) can be calculated in a linear time.

We use topological sort to find the distance of a single source to all other nodes.

Intuition: Iterate on nodes u in topological order. For each node v that is a neighbor of v, relax d[v].

What you need to know:

  • Run Time: O(m+n)
  • It CAN handle negative edges
  • It CANNOT handle negative cycles (there is no cycle in DAGs)

Breadth First Search Algorithm

Breadth First Search, BFS, can find the shortest path in a non-weighted graphs or in a weighted graph if all edges have the same non-negative weight. Without loss of generality, assume all weights are 1.

Intuition: BFS levelizes a graph, i.e., at each iteration i it visits the nodes at distance i from the source. Therefore, if the shortest path from source to a node is i, we will definitely find it in iteration i.

What you need to know about BFS:

  • Run Time: O(m+n)
  • All weights should be equal
  • It CANNOT handle negative weights
  • It CANNOT handle negative cycles

read original article here