Friday, January 29, 2010

Longest path

Find the longest path in a DAG
Pubblicato da a
Reazioni: 

1 comment:

  1. The standard linear-time shortest path algorithm for DAG (topologically sort - scan and relax edges) remains correct even when weight are negative. So you just add an auxiliary start node connected to every other node in the graph, and then launch the shortest-path algorithm for DAG using the start node as source and weighting each edge with -1.

    ReplyDelete

Subscribe to: Post Comments (Atom)