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 algorithm tries to relax all edges for every edge on the shortest path - followingly, only size(vertices) - 1 relax-iterations have to be computed.
==== Follow-up to Proposed Answer ====
While everything stated in the proposed answer is correct, the pseudo code proceeds to check for negative cycles, which is done by letting the algorithm run V times instead of V-1.
The reason is that, if there is a negative cycle, then some shortest path will be even shorter if you allow one more edge to be used. But since we only run V-1 times, we cannot use
this fact in the final negative cycle check.
[[User:Viktornordling|Viktornordling]] ([[User talk:Viktornordling|talk]]) 02:46, 24 January 2013 (UTC)
