- Forum
- General C++ Programming
- Bellman Ford number of edges
Bellman Ford number of edges
I'm using the Bellman Ford algorithm to create a routing table. You can see the algorithm here: http://www.geeksforgeeks.org/dynamic-programming-set-23-bellman-ford-algorithm/
How can I modify this algorithm to find the number of edges in each shortest path? My original idea was to keep an int for each path and increment it each time a shorter path was found at a given iteration. My reasoning was that each iteration i would yield all paths with a maximum length of i. The article I linked says this, but it appears to not be true. What can I do?
How can I modify this algorithm to find the number of edges in each shortest path? My original idea was to keep an int for each path and increment it each time a shorter path was found at a given iteration. My reasoning was that each iteration i would yield all paths with a maximum length of i. The article I linked says this, but it appears to not be true. What can I do?
Could you store u for v whenever the dist[v] is updated?
For example, the D gets dist "1", when evaluating BD, and later dist "-2", when evaluating ED. Therefore, you should store "E" for D at the end. Similarly, the E would have "B" and the B would have "A".
For example, the D gets dist "1", when evaluating BD, and later dist "-2", when evaluating ED. Therefore, you should store "E" for D at the end. Similarly, the E would have "B" and the B would have "A".
The way I ended up doing it was keeping track of the predecessor for each node, then backtracking from each node until I get to the source, keeping track of how many edges there are in the path.
Topic archived. No new replies allowed.