Alternative algorithms for finding the longest path in Directed Acyclic Graphs I am currently working on the method of finding the longest path in Directed Acyclic Graphs (DAC's). I wonder if there is another way to do it other than topological sorting. Is there any chance using the adjacency matrix to solve this problem?
 A: First, let me say that finding the longest path in a DAC using topological sorting works very well, and I wonder why you are searching for alternative methods. The topological sorting itself can be done in linear time, and finding the longest path using the topological sorting also works in linear time, giving you a very fast algorithm (which is quite unusual for these type of problems).
Secondly, I suppose you could look at the adjacency matrix to work out the longest path, and I would do it as follows. Say I have given an adjacency matrix, e.g.
$$\begin{bmatrix}
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
0 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\
1 & 0 & 0 & 1 & 1 & 0 & 0 & 0\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
0 & 0 & 0 & 1 & 0 & 0 & 0 & 1\\
0 & 0 & 1 & 0 & 0 & 0 & 0 & 1\\
0 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\
\end{bmatrix}
$$
The algorithm works as follows. Take the first row of the matrix, and find the first 1 in that row. When there are no 1's, it means that there is no out-going edge from the first vertex of the graph. Record that the longest path starting from row 1 was 0. Move on to the next row.
Find the first 1 in the second row. This appears in column 3. Therefore, move to row 3 and find the first 1. This appears in column 1, which we have already covered, and from which the longest path was 0. This gives a path of total length 2. Move on to the next 1 in row 3. This leads to row 4, which leads no where, again a path of total length 2. The next 1 in row 3 leads to row 5, which leads no where. In total, I can get a path of length 2 from row 2. Move to row 3.
Note that we already covered row 3 when checking row 2, and we found out that the longest path had length 1 for this row. Move to row 4.
Row 4 has no 1's, so record a 0 as the longest path starting from this row. Move to row 5.
Row 5 also has no 1's, so record a 0. Go to row 6.
The first 1 in row 6 appears in column 4, so we check out what we recorded in row 4, which was a 0. This thus gives a path length of 1. The second 1 of row 6 leads to row 8, so move to row 8. This row has a 1 in column 5, which we have already recorded as having a 0 length path as its longest path, so we record a 2. Move to row 7.
The first 1 appears in column 3, where we recorded a 1. So the longest path so far in this row is 2. Move to the next 1, which appears in row 8. In fact, we already covered row 8 in the steps we took for row 6, and we found a maximal path length of 1. So I can record a 2 for row 7. Move to row 8.
Row 8 has already been covered, and we recorded a 1.
Now I can just take the maximum value of all the path lengths that I recorded at each row. This value is 2, and could be obtained starting from vertex 2, 6, and 7.
This is how I would do it. Note that the algorithm becomes simpler and simpler to carry out the more rows you have covered, since you are recording more and more maximal path lengths while going through the rows.
