Talk:Bellman–Ford algorithm: Difference between revisions

Revision as of 11:55, 3 September 2011

Revision as of 12:15, 3 September 2011

Line 125:

The program I made based on the pseudocode didn't work until I made this change. Can anyone confirm that this is indeed the case (and not just some other bug in my program) and if so, correct the article? --[[User:Smallhacker|Smallhacker]] ([[User talk:Smallhacker|talk]]) 15:38, 3 March 2011 (UTC)

==== proposed answer ====

for i from 1 to size(vertices) - 1

for i from 1 to size(vertices) - 1

is correct.

in other other words: you intentionally leave one vertex out.

reason:

bellman ford computes single source shortest paths; meaning from one vertex ('''s''') to all others.

let a shortest path from '''s''' to an arbitrary vertex '''v''' contain ''k'' edges.

the distance from '''s''' to itself is known from the beginning and initialized with 0 (see initialization phase).

that means, the path ''p'' from s to v can be described as follows: ''p'' = ('''s''' = v₀, v₁, ..., v_k-1, v_k = '''v''').

so the vertex you can leave out is the source.

in the worst case the shortest path visits all vertices of the graph. these are size(vertices). but the path between '''s''' and '''v''' only contains size(vertices) - 1 edges.

the number of vertices without '''s''' is size(vertices) - 1. <span style="font-size: smaller;" class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/188.192.84.92|188.192.84.92]] ([[User talk:188.192.84.92|talk]]) 11:43, 3 September 2011 (UTC)</span><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->

the algorithm tries to relax all edges for every edge on the shortest path - followingly, only size(vertices) - 1 relax-iterations have to be computed.