25.1.4. Setting Up the Longest Path Problem

Let us continue to look at DAGs and in this section we will look at the different problem called identifying the Longest Path in a DAG.

So, recall that the directed acyclic graph is just a directed graph in which there is no directed path from any vertex back to itself, so it is direct and it is acyclic.

A Directed Acyclic Graph (DAG) is a special type of graph with arrows (directed) that does not loop back on itself (acyclic). In simpler terms, if you picture a graph as a flow of tasks, in a DAG you cannot go back to an earlier task once you've moved on. This property of DAGs is crucial for problems that involve scheduling or understanding dependencies.

Imagine you are building a piece of furniture. You need to follow a specific order: first, you must gather the materials, then you cut the wood, assemble the pieces, and finally, you can paint it. At each step, you cannot go back to a previous step. In this analogy, each task represents a vertex in a DAG, and the directions of your tasks (gathering → cutting → assembling → painting) represent the edges.

Any directed acyclic graph can be topologically ordered. If you think of the vertices has been 1 to n, you can write out 1 to n as a sequence in such a way that for every pair j, k which is an edge if j, k is an edge in my graph, then j will appear before k in the sequence. So, if you think of these as tasks it is dependencies means that I can do the task in such a way that before I do k, I would have finished it is dependence task j. So, this is called a topological sorting.

Topological sorting is an arrangement of the vertices in a graph where for every directed edge from vertex j to vertex k, j comes before k in the sequence. In terms of tasks, this means that you complete prerequisites (task j) before starting the dependent task (task k). This is useful for ensuring that tasks are done in the correct order based on their dependencies.

Continuing with the furniture analogy, imagine you have a list of tasks: gathering materials, cutting wood, assembling pieces, and painting. A topological sort would arrange these tasks in the necessary order: 'gather materials' must come before 'cutting wood', which in turn must come before 'assembly', and so on. This ensures that you can follow the steps logically without backtracking.

So, let us look at different question about DAGs. So, supposing we have this DAG and we imagine that the vertices represent courses and the edges are prerequisites. Now, these are courses that we have to do to may be complete the degree, every course requires a semester, but we can do more than one course in a semester. So, the question is, what is the minimum number of semesters that I need to complete this program consisting of these 8 courses, with these prerequisites.

In this context, courses are viewed as vertices, and prerequisites are the edges connecting them. To find out how many semesters (iterations) are required to complete all courses while adhering to prerequisite orders, we can model the problem using a DAG. The minimum number of semesters relates directly to the longest path in this graph, representing the sequence of dependencies that must be fulfilled.

Think of your degree as a set of building blocks. Some blocks can be placed directly, while others rely on supporting blocks to be placed first. For instance, to take advanced math, you need to complete basic math. Understanding how to manage the arrangement of your blocks (courses) allows you to minimize the time (semesters) needed to build your entire structure (complete your degree).

Now, this problem corresponds to asking for the longest path in the DAG. What we are saying is that it takes 5 semesters to complete 8, because there is a chain of dependencies, where 8 depends on 7, 7 depends on 6, 6 depends on say 3 or 4 it does not matter which one we choose and 3 depends on 1. This chain forces us to spend 4 semesters because it is a chain of length 4.

To complete a course (vertex) that has prerequisites (edges), we must count the longest dependency chain leading to that course. This longest path gives the required number of semesters to ensure each prerequisite is completed before moving on to dependent courses. Unlike other problems that may focus on shortest paths, here we emphasize the longest path that ensures fulfilling all dependencies.

Returning to the furniture analogy, suppose to complete the painting (course 8), you first have to complete the assembly (course 7), which requires you to have finished cutting and gathering materials (courses 6 and 3). If each task takes one semester, the longest path (which informs us how many semesters are needed) is determined by how many tasks must finish before you can start painting.

So, therefore in order to compute the longest path to k, I need to compute the longest path to all its incoming neighbours. Now, if we have arrange the vertices in topological order and we compute the longest path in that sequence, then when we get to k every incoming neighbour j will be on its left.

By arranging the vertices in a topological order, we can focus on calculating the longest path efficiently. As we process each vertex, we check its incoming neighbors (which must be completed first) and determine the maximum path length leading to each vertex. This approach allows us to incrementally compute the longest path without needing to backtrack or reanalyze previously completed vertices.

Think of this process as building a foundation for a house (topological order) before constructing the walls and roof. You start with the ground layer, ensuring it’s solid before adding on to it. Similarly, by processing in a topological order, we can build up our understanding of the longest paths, layer by layer.

So, this pseudo code for longest path as we saw is very similar to what we did for the topological sort, we just have keep track of this extra longest path value. So, this has complexity order n squared for the same reason that we had found that topological short with adjacency matrix or order n squared.

The algorithm for finding the longest path in a DAG is often similar to that of a topological sort, with an additional step to track the longest path values. Its complexity, in the basic implementation using an adjacency matrix, is O(n²), primarily because we must examine each vertex and its neighbors. However, optimizations exist, such as using an adjacency list, that can reduce this time complexity thanks to more efficient management of edges.

Imagine using a checklist (adjacency matrix) to track the longest path in your project. Each task checked off adds to a running total (the path length). While checking off tasks one by one has its limitations, organizing your project in a way that focuses solely on the critical tasks (adjacency list) could save you time and allow you to work more efficiently.

--