Longest path from node 0, in a acyclic directed graph(DAG)
I'm having some problems finding the longest path from node 0 to any other node, as long as it is the longest path from node 0.
I have done topological sorting from node 0.
I have also made another algorithm which returns a 2-D matrix of relative distance between the nodes.
For example:
A DAG of order 10 has the following adjacency list and matrix:
10(order)
0 0 0 0 0 0 0 0 1 0
1 0 0 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 0
1 0 0 0 0 0 0 1 1 1
1 1 0 0 1 0 0 1 0 0
0 1 1 1 0 0 0 0 0 0
1 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0
10 (order)
8
0
5
0 7 8 9
0 1 4 7
1 2 3
0 2
9
The distance matrix values for the above graph are:
00 10 10 10 10 10 10 10 01 02
01 00 10 10 10 10 10 10 02 03
10 10 00 10 10 10 10 10 10 10
02 02 03 00 02 01 10 02 03 03
01 10 02 10 00 10 10 01 01 01
01 01 02 10 01 00 10 01 02 02
02 01 01 01 03 02 00 03 03 04
01 10 01 10 10 10 10 00 02 03
10 10 10 10 10 10 10 10 00 01
10 10 10 10 10 10 10 10 10 00
The distance matrix above shows the shortest path between nodes, unfortunatley I need to find the longest path.
Can someone please help me with the algorithm for that, I have been awake for a long time and I still can't figure it out.....