🙏

জয়  শ্রী  রাম

🕉

---

We will be finding the longest path between two vertices in an edge-weighted Directed Acyclic Graph that may be positive or negative.

Prerequisite for this chapter is Topological Sort w/ Vertex Relaxation.

If we negate all the edge weights in a given graph, and find the shortest distance between vertex A and vertex B in the modified graph, then that shortest path in the modified graph actually becomes the longest path between vertex A and vertex B in the original graph. We will be using this observation to construct our Longest Paths Algorithm.
So, we will be using the concept algorithm used to find shortest paths in the chapter Topological Sort w/ Vertex Relaxation, and then there are two simple ways to convert that to longest paths algorithm, as described below:

1. Modify the given graph by negating all edge weights. Find shortest path between vertex A and vertex B in this modified graph.
   This shortest path in the modified graph is the longest path between A and B in the originally given graph.
   See Implementation #1.
2. The second approach would be:
   Initialize distance[i] to -INFINITY, instead of +INFINITY, for all i except for the source vertex.
   While computing longest paths, distance[] array keeps track of longest distance from source to vertex i.
   
   Do a stretch which is opposite of relaxation:
   

           
   if (distance[v] < distance[u] + weight[u][v]) {
      distance[v] = distance[u] + weight[u][v]
   }           
               

   
   See Implementation #2.

Implementation #1

Login to Access Content

Implementation #2

Login to Access Content

Time Complexity:

Topological Sort takes O(E + V). Stretching takes another O(E + V) since we are doing a vertex stretching for all vertices and overall stretching all the edges.
Overall O(E + V), where E = total number of edges in the given graph and V = total number of vertices in the given graph.

Note:

This algorithm does not work for a graph which has a cycle. The graph needs to be a DAG. Topological Sort is not applicable for cyclic graphs.
Now you may ask why can't we use Dijkstra's Algorithm when there is a cycle in the given graph ?
Conversion of a Shortest Paths Algorithm to a Longest Paths Algorithm is based on negating the edge weights, and Dijkstra's Algorithm does not work on a graph which has edges with negative weights.
The 2nd approach wouldn't work either for Dijkstra's Algorithm since after stretching a vertex you cannot just select the immediate neighboring vertex with the longest distance from the vertex and mark that as processed, because that wouldn't necessarily give you the correct result as the longest path to that neighboring vertex may be through a vertex which has lower distance from source at the time of the vertex stretch.
Let's look at the graph below:

     
   ___________5____\ B
  /                /     
 /              
A____15____________\  C
\                  / / \
 2                    |
  \                   |
  _\|  _____20________|
    D

If we apply approach similar to that in Dijkstra's Algorithm and try to find longest path between A and C then while stretching (opposite of relaxation operation while computing shortest paths) we will see that weight of AB is 5, AC is 15 and that of AD is 2. Since weight of AC is highest among these three we would remove vertex C from the maxHeap (notice how we are using max heap instead of min heap, because it is a longest paths problem) and mark that as processed. But clearly it is wrong. The longest path to C (from source vertex A) is through D. This explains why Dijkstra's Algorithm cannot be used to compute Longest Paths problem.

Problems Solving using Longest Paths Algorithm

Please see Parallel Job Scheduling chapter to find out how Longest Paths Algorithm can be useful to solve real world problems.

Instructor: