simple graph traversal using the Bellman-Ford algorithm
I am a little stuck on a problem in which we are supposed to fill in the values after running two iterations of the Bellman-Ford algorithm on a basic directed graph.
I believe I understand the first iteration and I understand the concept of "relaxing edge weights" as shorter paths are found. However, I don't see how the second iteration, in this particular problem, would yield any shorter paths than the ones located in the first iteration.
For example, I know that visiting node 'C' via the path of starting at node A, then going to node 'B' then going to node 'C' would have a total "cost" of 6+8 = 14. However, because the traversal order of this graph is: AB, AC, BC, BD, etc., the cost of reaching node C via node B (14) would never be saved because a shorter path to C directly from A would have already been found (yielding a cost of 7) I don't see how any additional iterations would give a shorter path length from A to C for example which seems to be the significance of the subsequent iterations.
upon closer inspection it appears that the data is indeed correct. It's just a poorly formatted question in the sense that the second iteration does not, in this particular case, yield any further "relaxation" of edges and is therefore misleading to those expecting to see a difference over the second iteration.