4 ms·
It doesn't seem like the shortest path on a graph with negative cycles would be defined for any algorithm.
by rcme 4y ago
It doesn't seem like the shortest path on a graph with negative cycles would be defined for any algorithm.
- hammock 4y agoRight
- tejtm 4y ago"single source shortest acyclic path" would be the closest term that could make sense
- tylerhou 4y agoNit: In a graph with negative cycles, shortest paths are still well-defined for vertices s to t if there is no path from s to a negative cycle or if there is no path from a negative cycle to t. In the simplest case, suppose you have a graph with exactly one negative cycle that is completely isolated from the rest of the graph. The shortest paths between vertices in the negative cycle are not well-defined, but the shortest paths in the rest of the graph are well-defined. In general, look at the meta-DAG induced by the SCC decomposition of the graph. Mark any meta-vertices whose SCC contains some negative cycle. For s, t in the original graph, the distance from s to t is well-defined iff there exists no path from s's meta-vertex to t's meta-vertex in the meta-graph that traverses through a marked meta-vertex. (Proof left to the reader.)