Shortest and Longest Path Algorithms: Job Interview Cheatsheet

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)

Below is the implementation of shortest path in DAG using topological sort:

Detailed implementation of topological sort in C++ is as follows:

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

The Longest Distance Problem

The sister problem to finding the shortest path is to find the longest path. But first notice that there is a huge confusion when we talk about the longest path:

The longest path problem commonly means finding the longest simple path.

The shortest path problem (as discussed above), however, focuses on finding the shortest (simple or non-simple) path.

So, in the literature even when people talk about finding the longest path, they usually mean finding the longest simple path.

Transformation to -G

The longest simple path problem can be solved by converting G to -G (i.e. inverting the sign of the weight of each edge in the original G), and then calculate the shortest simple path.

Notice that if -G has no negative cycles, finding the shortest simple path is the same as finding the shortest path which can be solved in polynomial time using above algorithms.

What you need to know about the longest simple path problem

• Finding the longest simple path in general is NP-Hard. This can easily be shown by reducing from the Hamiltonian Cycle problem.
• It follows that finding the longest simple path in the presence of positive cycles in G is NP-hard.
• If there is no positive cycles in G, the longest simple path problem can be solved in polynomial time by running one of the above shortest path algorithms on -G.

And here comes an interesting point about finding the shortest simple path in a graph that we don’t hear often:

Finding the shortest simple path in a graph is NP-hard.

This can be proved by using -G transformation to the problem of finding the longest simple path.

To understand it better, suppose there is a negative cycle in G. In this case none of our famous algorithms can find a shortest path simple because it doesn’t exit. However, there is still a shortest simple path in the graph where no vertices repeat. Finding that shortest simple path is NP-hard!

Longest Path in DAGs

If G is a DAG, because there is no cycles, the problem of finding longest simple path can be solved using topological sort in linear time. The solution is similar to the solution for finding the shortest distance in DAGs except that we take the maximum value as we relax the distances.

Please let me know if you heard about interesting questions about shortest and longest path algorithms during job interviews. Good luck on your interview!