Shortest positive path in a directed acyclic graph

0
votes

We are given a directed acyclic graph with arbitrary weights on edges and two specific nodes, s and t, where in-degree of s and out-degree of t is 0. How to determine the shortest path from s to t that has positive cost?

1
pathdirected-acyclic-graphsshortest
my guess is en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm - helt
Bellman-Ford will give the shortest s-t path, but it can have negative cost. Then what should we do? We need the shortest path between s and t that has positive cost. - Heisenberg
either modify bf so that it is prevented from moving along negative edges if they reduce the current cost too much, or do a loop: search shortest path; if c(path) < 0 remove as many negative edges that are contained in the path, then search again. or do edge removal one by one. (no warranty if you dont get all points for that homework) - helt

1 Answers

0
votes

Use a modified Bellman-Ford, which removes edges from the graph if a resulting shortest path cost is <0 until you reach a cost, that is not <0.