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.
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