MHB What Edges Are Selected in the Bellman-Ford Algorithm?

  • Thread starter Thread starter evinda
  • Start date Start date
AI Thread Summary
The Bellman-Ford algorithm detects negative cycles by relaxing all edges in the graph repeatedly for a total of |V|-1 iterations, where |V| is the number of vertices. Unlike Dijkstra's algorithm, which selects edges based on the closest vertex using a priority queue, Bellman-Ford evaluates every edge during each iteration. The goal is to replace the current distance to a vertex with a shorter path if one is found. This process continues until no further reductions can be made or until all edges have been processed. Understanding this method is crucial for grasping how the algorithm functions in finding the shortest paths and detecting negative cycles.
evinda
Gold Member
MHB
Messages
3,741
Reaction score
0
Hello! (Wave)

I am reading an example about the Bellman-Ford algorithm in order to understand it, but I don't really know what edges we pick from the second step and at the following ones.

Here is the example I am looking at, where they want to detect if there is a negative cycle.

bf1.PNG


bf2.PNG


bf3.PNG


bf4.PNG


bf5.PNG


bf6.PNG

Could you explain to me the idea that we follow? (Thinking)
 
Physics news on Phys.org
evinda said:
I am reading an example about the Bellman-Ford algorithm in order to understand it, but I don't really know what edges we pick from the second step and at the following ones.

Here is the example I am looking at, where they want to detect if there is a negative cycle.

Could you explain to me the idea that we follow?

Hi evinda!

Wiki explains:
Like Dijkstra's algorithm, Bellman–Ford proceeds by relaxation, in which approximations to the correct distance are replaced by better ones until they eventually reach the solution. In both algorithms, the approximate distance to each vertex is always an overestimate of the true distance, and is replaced by the minimum of its old value and the length of a newly found path.

However, Dijkstra's algorithm uses a priority queue to greedily select the closest vertex that has not yet been processed, and performs this relaxation process on all of its outgoing edges; by contrast, the Bellman–Ford algorithm simply relaxes ''all'' the edges, and does this$|V|-1$ times, where $|V|$ is the number of vertices in the graph.


but I don't really know what edges we pick from the second step and at the following ones.

We pick all edges and see if we can make reduce the value of the target node of each edge. 🤔
 
Klaas van Aarsen said:
Hi evinda!

Wiki explains:
Like Dijkstra's algorithm, Bellman–Ford proceeds by relaxation, in which approximations to the correct distance are replaced by better ones until they eventually reach the solution. In both algorithms, the approximate distance to each vertex is always an overestimate of the true distance, and is replaced by the minimum of its old value and the length of a newly found path.

However, Dijkstra's algorithm uses a priority queue to greedily select the closest vertex that has not yet been processed, and performs this relaxation process on all of its outgoing edges; by contrast, the Bellman–Ford algorithm simply relaxes ''all'' the edges, and does this$|V|-1$ times, where $|V|$ is the number of vertices in the graph.

We pick all edges and see if we can make reduce the value of the target node of each edge. 🤔


I see... Thank you! (Mmm)
 
I was reading documentation about the soundness and completeness of logic formal systems. Consider the following $$\vdash_S \phi$$ where ##S## is the proof-system making part the formal system and ##\phi## is a wff (well formed formula) of the formal language. Note the blank on left of the turnstile symbol ##\vdash_S##, as far as I can tell it actually represents the empty set. So what does it mean ? I guess it actually means ##\phi## is a theorem of the formal system, i.e. there is a...

Similar threads

Back
Top