Using the Bellman-Ford algorithm: whats the proper way of traversing each edge?

Question

Im doing a homework problem where I need to run the bellman-ford algorithm starting at vertex z. It wants me to "In each pass, relax edges in the same order as in the figure, and show the d and pi values after each pass." From what i understand I thought this algo traverses the graph like a BFS which makes sense from the figure they want me to use, so I cant see how the same path would work. If anyone could point me in the right direction by pointing out how to start it would be very useful. The question, and the figure the question is referring to:

Answer 1

I'll try to point out your mistake.

I thought this algo traverses the graph like a BFS

This is not true. This algorithm iterates over all the edges of the graph repeatedly, and "relax" them until it get to a stable state (when no relaxation can be done anymore)

The example you attached is a bit confusing, and resembles a BFS execution. this is because that in each iteration they bold only the edges that have effected the nodes value (The edges that were relaxed).

So, to answer your question, Choose any order for the edges, and start so-called "relaxing" them. For each edge, set its pointing node d value to be the shortest distance so far from Z, and set it's pi to be it's predecessor node. repeat this until all the values are stable.

Hope that answers your question.

Answer 2

As Ido.Co said, in Bellman Ford there is no particular order of scanning/iterating. But it is said scanning breadth first way, execution is faster.