 Solution

Initialize $d[s]=0$ and $d[v]=\infty$ elsewhere. Perform $|V|-1$ full passes over the directed edges, applying edge relaxation $d[v]\leftarrow \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 $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|\ge 1$.