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: (if not, see the section for longest path below) Did you know finding the shortest simple path in a graph is NP-hard? 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 has , where G(V, E) V = {1, 2, … , n} , |V| = n |E| = m For the shortest path problem, we assume we are after the shortest path, i.e., vertices can repeat. Also, we assume the edge weights can be an integer value, i.e., positive, negative, or zero. non-simple problem only requires the shortest distance between nodes, whereas 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. The Shortest Distance The Shortest Path Problem Floyd-Warshall Algorithm Floyd-Warshall is the simplest algorithm: : We calculate the shortest possible path from node to using nodes only from the set between them. d(i,j,k) represents the shortest distance between i, j using only k nodes. We can write: Quick Intuition i j {1, 2, …, k} as intermediate points 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++: < < >> floydWarshal( < < >> &graph) { < < >> d(graph.size(), < >(graph.size())); ( i = ; i < graph.size(); ++i) { ( j = ; j < graph.size(); ++j) { d[i][j] = graph[i][j]; } } ( k = ; k < graph.size(); k++) ( i = ; i < graph.size(); ++i) ( j = ; j < graph.size(); ++j) d[i][j] = ::min(d[i][j], d[i][k] + d[k][j]); d; } // Floyd-Warshall Algorithm for finding the shortest distance vector vector long long vector vector int vector vector long long vector long long //Initialize d for int 0 for int 0 for int 0 for int 0 for int 0 std return 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. Keep a list of visited nodes. At each step: Intuition: Find the unvisited node with shortest distance u Relax the distance of neighbors of u Add to the visited list and repeat u Below is Dijkstra’s implementation in C++: < > dijkstra( < < >> &graph, source) { < > d(graph.size()); < > s; ( i = ; i < graph.size(); i++) { d[i] = graph[source][i]; } s.push_back(source); (s.size() < graph.size()) { u = findMinInDButNotInS(d, s); s.push_back(u); ( j = ; j < graph.size(); j++) { d[j] = ::min(d[j], d[u] + graph[u][j]); } } d; } // Dijkstra shortest distance vector long vector vector int int vector long vector int for int 0 while //Find minimum int //Relax for int 0 std return View gist on Github What You Need to Know about Dijkstra’s Algorithm: The run-time is: ² simple form. With min-heap: With Fibonacci heap: O(n ) O( (m+n)log(n) ). 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++: < > dijkstraPriorityQueue( < < >> &graph, source) { priority_queue<pair< , >, <pair< , >>, greater<pair< , >>> q; < > d(graph.size(), INT_MAX); d[source] = ; q.push(make_pair( , source)); (!q.empty()) { u = q.top().second; q.pop(); ( j = ; j < graph.size(); j++) { (d[j] > d[u] + graph[u][j]) { d[j] = d[u] + graph[u][j]; q.push(make_pair(d[j], j)); } } } d; } // Dijkstra shortest distance vector long vector vector int int // Queue of pairs of distance to node number int int vector int int int int vector long 0 0 while // Find minimum int // Relax distances // Rather than decreasing the values in the queue, // we just add the updated distance to the queue again. for int 0 if return View gist on Github Bellman-Ford Algorithm This algorithm finds shortest distance from source to all other nodes. We have two loops: Intuition: We have two loops: Intuition: The inner loop: We iterate on all edges. At each iteration we relax the distances by using edges from to . 0 j The outer loop: We repeat the inner loop times n-1 Bellman-Ford Algorithm. Picture taken from here . After the iteration of the outer loop, the shortest paths with at most edges are calculated. There can be maximum edges in any simple path, so we repeat times. i-th i n - 1 n - 1 Below is an implementation of Bellman-Ford algorithm in C++. < > bellmanFord( < < >> &graph, source) { < > d(graph.size(), INT_MAX); d[source] = ; ( i = ; i < graph.size() - ; i++) { ( u = ; u < graph.size(); u++) ( v = ; v < graph.size(); v++) d[v] = ::min(d[v], d[u] + graph[u][v]); } d; } // BellmanFord Algorithm vector long vector vector int int vector long 0 for int 0 1 for int 0 for int 0 std return 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. Iterate nodes of the graph in topological order. For each node that is a neighbor of , relax Intuition: u v u 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: < > shortestPathTopo( < < >> &graph, source) { < > d(graph.size(), INT_MAX); d[source] = ; < > sorted = topologicalSortDFS(graph); ( n : sorted) { ( j = ; j < graph.size(); j++) { (graph[n][j] != INT_MAX) { d[j] = min(d[j], d[n] + graph[n][j]); } } } d; } // Shortest path using topological sort vector long vector vector int int vector long 0 vector int for auto for int 0 // Relax outgoing edges of n if return View gist on Github Detailed implementation of topological sort in C++ is as follows: < > topologicalSortDFS( < < >> &graph) { < > result; < , > visited; < > unvisited; ( i = ; i < graph.size(); i++) { unvisited.insert(i); } (!unvisited.empty()) { DFS(graph, visited, unvisited, result, *(unvisited.begin())); } ::reverse(result.begin(), result.end()); result; } { (visited[n] == ) { << << ; ; } (visited[n] == ) { ; } visited[n] = ; ( j = ; j < graph.size(); j++) { (j != n && graph[n][j] != INT_MAX) { DFS(graph, visited, unvisited, sorted, j); } } unvisited.erase(n); visited[n] = ; sorted.push_back(n); } // Topological Sort Using DFS vector int vector vector int vector int // map of node to 0: not visited, 1: being visited, 2: visited unordered_map int int set int for int 0 // While there is unvisited nodes while std return //----------------------------------------------------- // 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 ( < < >> &graph, < , > &visited, < > &unvisited, < > &sorted, n) vector vector int unordered_map int int set int vector int int if 1 cout "Detected cycle!" endl return if 2 return 1 for int 0 if 2 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 BFS levelizes a graph, i.e., at each iteration it visits the nodes at distance from the source. Therefore, if the shortest path from source to a node is , we will definitely find it in iteration Intuition: i i i 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 path. simple 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 path. simple Transformation to -G The longest simple path problem can be solved by converting to inverting the sign of the weight of each edge in the original ), and then calculate the . G -G (i.e. G shortest simple path Notice that if 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. -G 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 is NP-hard. G If there is no positive cycles in , the longest simple path problem can be solved in polynomial time by running one of the above shortest path algorithms on . G -G And here comes an interesting point about finding the shortest path in a graph that we don’t hear often: simple Finding the shortest path in a graph is NP-hard. simple This can be proved by using transformation to the problem of finding the longest simple path. -G To understand it better, suppose there is a negative cycle in . 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 path in the graph where no vertices repeat. Finding that shortest simple path is NP-hard! G simple Longest Path in DAGs If 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. G 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++:
