= Solution
Initialize $d[s]=0$ and $d[v]=\infty$ elsewhere. Perform $|V|-1$ full passes over the directed <edges>, applying <edge relaxation> $d[v]\gets\min\{d[v],d[u]+w(u,v)\}$ whenever $d[u]$ is finite. For an <undirected graph>, process each <edge> in both directions. Stop early if a pass makes no change.
Each finite label records the cost of a discovered <directed walk>, so it never understates the true infimum. After $t$ passes, relaxation has propagated along every route of at most $t$ <edges>, so the label is no greater than the cost of any such route. If no reachable negative-cost closed walk exists, an optimal route can be chosen without repeated <vertices> and has at most $|V|-1$ <edges>. These inequalities prove that the final labels are the desired <shortest path> lengths.
An additional pass checks for an improving <edge> from a reachable <vertex>. If one exists, report a reachable negative-cost cycle: finite shortest distances cannot be assigned to <vertices> reachable from that cycle. Mark those <vertices> by forward reachability if individual $-\infty$ answers are wanted. In particular, a reachable negative undirected <edge> becomes a negative two-arc closed walk under the bidirected interpretation; generic signed weights do not guarantee finite answers.
Each pass costs $O(|E|)$, giving \b[$O(|V||E|)$] for the usual <Bellman-Ford algorithm> bound. Including initialization gives $O(|V|+|V||E|)$, which also handles an edgeless <graph> honestly; these coincide in order when $|E|\ge1$.
Back to article page
