First of all let’s clear thing up:
Finding the longest path of a graph algorithm is NOT the inverse of Dijkstra’s algorithm of finding the shortest path. In fact finding the longest path of a graph in NP-Hard problem.
In our case, the graph is a tree-shaped graph, more like a triangle.
1 2 3 4 5 6 7 |
8 / \ 1 4 / \ / \ 4 2 0 / \ / \ / \ 9 1 9 4 |
Our goal here is to find the longest path from top to bottom.
Example:
Note how we select each node leading us to the longest path:
1 2 3 4 5 6 7 |
>8 / \ 1 >4 / \ / \ 4 >2 0 / \ / \ / \ 9 1 >9 4 |
STOP and think about an algorithm to solve this problem.
I will be posting the algorithm along with an implementation in C++ sometimes soon.
Leave a reply