Nit: 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

Nit: 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.)