longest path from start node to any other.

[hubertson]

I am thinking about an algorithm to find the longest path from one node to the
other in a DAG(directed acyclic graph) in linear time.
Can you help me with advices?
Can you give me a solution?
I thought about inverting the edge weight and then finding the shortest path.

Thank you.

[D_Drmmr]

Another way to do it is to find an ordering of the nodes, such that all arcs point 'from right to left' (I forgot the name for it). This can be done in linear time and needs to be done only once, if your graph doesn't change.
Once you have this ordering, you iterate over the nodes in that order and iterate over the arcs leaving the current node. Set the label of the other node (where the arc comes in) to the max. of its current label and the label of the current node plus the weight of the arc.
This method only works on acyclic directed graphs and its running time is linear in the number of edges.

[D_Drmmr]

Topological ordering - that's the name.
Pseudocode to find a topological order in an acyclic directed graph G = (N, A)

Order = empty;
for (i = 0; i < n; ++i) {
Select n from N, with in-degree equal to 0;
Add n to the end of Order;
Remove n and all outgoing arcs from G;
}

The in-degree is the number of incoming arcs in a node. When the algorithm is done, Order contains the topological order of the nodes.