Initialize and every other tentative distance to infinity. The Bellman-Ford algorithm repeatedly relaxes every directed edge:
for v in V: d[v] = infinity; parent[v] = none
d[s] = 0
repeat |V|-1 times:
changed = false
for each edge (u,v) of weight w:
if d[u] != infinity and d[u] + w < d[v]:
d[v] = d[u] + w
parent[v] = u
changed = true
if not changed: break
for each edge (u,v) of weight w:
if d[u] != infinity and d[u] + w < d[v]:
report a reachable negative-weight cycleAn unreachable vertex retains infinity. A reachable negative-weight cycle prevents finite shortest-walk distances for vertices reachable from that cycle, so the detection case must not be reported as an ordinary finite answer. With edge-list scans the worst-case work is , conventionally stated as , and the auxiliary storage is beyond the graph.
Every finite distance label is the weight of a discovered directed walk, so it can never underestimate a finite shortest-path distance. After complete passes, each label is at most the cost of every source-to-vertex path using at most edges. To prove that assertion, consider such a path's last edge : after the previous pass, already has a label no greater than the prefix cost, and the current pass relaxes that last edge. In-place improvements can only make the label smaller, preserving the assertion.
When no negative-weight cycle is reachable, any repeated-vertex portion of an optimal walk can be removed without increasing its cost. Some shortest path therefore has at most edges. The two bounds meet after that many passes, proving correctness. If a complete pass makes no change, all edge relaxation inequalities already hold and further passes cannot improve anything. A further strict relaxation after passes implies a reachable negative cycle by the same simple-path bound.
Bellman–Ford permits negative edge weights, and can detect a reachable negative-weight cycle. The usual settled-label Dijkstra's algorithm requires nonnegative weights for its correctness argument. Negative edges are not themselves a problem for Bellman–Ford when no relevant negative cycle exists.
Use minimum-hop shortest paths by minimizing the lexicographic order pair : total weight first, number of edges second. Extend a pair across an edge of weight by adding , and compare the full pair in both the priority queue and relaxation:
for v in V: key[v] = (infinity,infinity)
key[s] = (0,0)
Q = indexed min-priority-queue containing all vertices, keyed by key
while Q is not empty:
u = extract-min(Q)
if key[u].distance == infinity: break
for each edge (u,v) of weight w with v still in Q:
candidate = (key[u].distance + w, key[u].hops + 1)
if candidate <lex key[v]:
key[v] = candidate
decrease-key(Q,v,candidate)
for v in V: best[v] = key[v].hopsAll weights are positive, so extending a path strictly increases its first component. The usual Dijkstra's algorithm settled-label proof therefore applies to these ordered pairs: no path through a not-yet-settled vertex can later improve an extracted minimum. Among equal minimum weights, the secondary component selects the fewest edges. Merely breaking extraction ties by vertex name would not implement this objective.
With a binary heap and adjacency lists, the bound is , with extra storage. Unreachable vertices have
best = infinity. In the paper's example, the resulting pairs in order are , so the requested edge counts are . Articles by others on the same topic
There are currently no matching articles.