Content deleted Content added
No edit summary |
→Algorithm description: Added comment. Tags: Mobile edit Mobile web edit |
||
Line 20:
#Second, the [[Bellman–Ford algorithm]] is used, starting from the new vertex {{mvar|q}}, to find for each vertex {{mvar|v}} the minimum weight {{math|''h''(''v'')}} of a path from {{mvar|q}} to {{mvar|v}}. If this step detects a negative cycle, the algorithm is terminated.
#Next the edges of the original graph are reweighted using the values computed by the Bellman–Ford algorithm: an edge from {{mvar|u}} to {{mvar|v}}, having length {{tmath|w(u,v)}}, is given the new length {{math|''w''(''u'',''v'') + ''h''(''u'') − ''h''(''v'')}}.
#Finally, {{mvar|q}} is removed, and [[Dijkstra's algorithm]] is used to find the shortest paths from each node {{mvar|s}} to every other vertex in the reweighted graph. This is quite interesting.
==Example==
| |||