Content deleted Content added
→New preprint: Reply |
No edit summary |
||
Line 41:
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.
As for what '''u''' is supposed to be, '''(u, v)''' is the entire edge, starting at vertex '''u''' and finishing at vertex '''v'''.
== Pop up shortest-path figure ==
| |||