Talk:Bellman–Ford algorithm: Difference between revisions

Revision as of 15:39, 3 March 2011

Revision as of 11:43, 3 September 2011

Line 109:

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)

for i from 1 to size(vertices) - 1

is correct.

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

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

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

so the vertex you can leave out is the source.

the number of vertices without '''s''' is size(vertices) - 1.