Tell me, please, how is the path related to the step number in the loop when finding the shortest path?
|
1 answer
The Bellman-Ford method is based on the idea of ​​dynamic programming. At step k outer loop, it finds the shortest path containing at most k edges. Thus, at step n-1 (the last step), we have the shortest paths in the full sense of the word (if the path does not go through a negative cycle).
Zealint Zealint
2,484 one 7 18
- Thank you. Another question. There is a graph with a negative cycle. How to select from the entire graph those vertices that form this cycle with the help of an array of parents? - alex77
- Well, for example, so. If
jis a vertex andi=p[j]is the previous one, then ifd[j]>d[i]+s[i,j], whered[]is an array of the shortest path (the result of the algorithm), ands[i,j]is the length of the edge(i,j), then the vertices i and j are included in the cycle of negative weight. We need to relax this edge and see if there are any more pairs of vertices. Perhaps this is not the only way, it is generally useful to read this , there are answers to all your questions. - Zealint
|
c#? - Grundy