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:

Quick 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. d(i,j,k) represents the shortest distance between i, j using only k nodes. We can write:

d(i,j,k) = min(d(i,j,k-1), d(i,k,k-1)+ d(k,j,k-1))

The following picture shows the intuition:

Shortest path from i,j using k nodes can be calculated by comparing the shortest path from i to j using k-1 nodes and the sum of i to k and k to j using k-1 nodes

Below is a video clearly explaining the Floyd-Warshall Algorithm:

Below is the implementation in C++:

// Floyd-Warshall Algorithm for finding the shortest distance

vector<vector<long long>> floydWarshal(vector<vector<int>> &graph) {
    vector<vector<long long>> d(graph.size(),
                                vector<long long>(graph.size()));

    //Initialize d
    for (int i = 0; i < graph.size(); ++i) {
        for (int j = 0; j < graph.size(); ++j) {
            d[i][j] = graph[i][j];
        }
    }

   for (int k = 0; k < graph.size(); k++)
    for (int i = 0; i < graph.size(); ++i)
      for (int j = 0; j < graph.size(); ++j)
        d[i][j] = std::min(d[i][j], d[i][k] + d[k][j]);

    return d;
}

View gist on Github

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
It CAN 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:

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

Below is Dijkstra’s implementation in C++:

// Dijkstra shortest distance
vector<long> dijkstra(vector<vector<int>> &graph, int source) {

    vector<long> d(graph.size());
    vector<int> s;
    for (int i = 0; i < graph.size(); i++) {
        d[i] = graph[source][i];
    }

    s.push_back(source);

    while (s.size() < graph.size()) {
        //Find minimum
        int u = findMinInDButNotInS(d, s);
        s.push_back(u);

        //Relax
        for (int j = 0; j < graph.size(); j++) {
            d[j] = std::min(d[j], d[u] + graph[u][j]);
        }
    }
    return d;
}

View gist on Github

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++:

// Dijkstra shortest distance
vector<long> dijkstraPriorityQueue(vector<vector<int>> &graph,
                                   int source) {

    // Queue of pairs of distance to node number
    priority_queue<pair<int, int>, vector<pair<int, int>>,
                   greater<pair<int, int>>>
            q;
    vector<long> d(graph.size(), INT_MAX);
    d[source] = 0;

    q.push(make_pair(0, source));

    while (!q.empty()) {
        // Find minimum
        int u = q.top().second;
        q.pop();

        // Relax distances
        // Rather than decreasing the values in the queue,
        // we just add the updated distance to the queue again.
        for (int j = 0; j < graph.size(); j++) {
            if (d[j] > d[u] + graph[u][j]) {
                d[j] = d[u] + graph[u][j];
                q.push(make_pair(d[j], j));
            }
        }
    }
    return d;
}

View gist on Github

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++.

// BellmanFord Algorithm
vector<long> bellmanFord(vector<vector<int>> &graph, int source) {
    vector<long> d(graph.size(), INT_MAX);
    d[source] = 0;

    for (int i = 0; i < graph.size() - 1; i++) {
        for (int u = 0; u < graph.size(); u++)
            for (int v = 0; v < graph.size(); v++)
                d[v] = std::min(d[v], d[u] + graph[u][v]);
    }
    return d;
}

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

View gist on Githu

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 nodes u of the graph in topological order. For each node v that is a neighbor of u, relax d[v] using the following:

d[v]=min(d[v], d[u] + w(u,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:

// Shortest path using topological sort
vector<long> shortestPathTopo(vector<vector<int>> &graph, int source) {
    vector<long> d(graph.size(), INT_MAX);
    d[source] = 0;
    vector<int> sorted = topologicalSortDFS(graph);
    for (auto n : sorted) {
        for (int j = 0; j < graph.size(); j++) {
            // Relax outgoing edges of n
            if (graph[n][j] != INT_MAX) {
                d[j] = min(d[j], d[n] + graph[n][j]);
            }
        }
    }
    return d;
}

View gist on Github

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

// Topological Sort Using DFS
vector<int> topologicalSortDFS(vector<vector<int>> &graph) {
    vector<int> result;

    // map of node to 0: not visited, 1: being visited, 2: visited
    unordered_map<int, int> visited;
    set<int> unvisited;

    for (int i = 0; i < graph.size(); i++) {
        unvisited.insert(i);
    }
    // While there is unvisited nodes
    while (!unvisited.empty()) {
        DFS(graph, visited, unvisited, result, *(unvisited.begin()));
    }

    std::reverse(result.begin(), result.end());
    return result;
}
//-----------------------------------------------------
// Recursively visits nodes
// If all children of a node is visited, adds it to sorted
// Marks nodes 0: not visited, 1: being visited, 2: visited
void DFS(vector<vector<int>> &graph, unordered_map<int, int> &visited,
         set<int> &unvisited, vector<int> &sorted, int n) {
    if (visited[n] == 1) {
        cout << "Detected cycle!" << endl;
        return;
    }

    if (visited[n] == 2) {
        return;
    }

    visited[n] = 1;

    for (int j = 0; j < graph.size(); j++) {
        if (j != n && graph[n][j] != INT_MAX) {
            DFS(graph, visited, unvisited, sorted, j);
        }
    }
    unvisited.erase(n);
    visited[n] = 2;
    sorted.push_back(n);
}

View gist on Github

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!

Check my video on Graph representation in C++: