[go: up one dir, main page]
Scribd
Upload
9 views2 pages

cmpe232_lecture_notes06

The document discusses the Bellman-Ford Algorithm, which is used for finding the shortest paths in general graphs, particularly when negative-weighted edges are present. It outlines the algorithm's process, time complexity of O(V.E), and the potential issue of endless loops caused by negative cycles. A comparison with Dijkstra’s and DAGSP algorithms highlights the strengths and weaknesses of each approach in handling different graph conditions.

Uploaded by

vehiri3156
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
9 views2 pages

cmpe232_lecture_notes06

The document discusses the Bellman-Ford Algorithm, which is used for finding the shortest paths in general graphs, particularly when negative-weighted edges are present. It outlines the algorithm's process, time complexity of O(V.E), and the potential issue of endless loops caused by negative cycles. A comparison with Dijkstra’s and DAGSP algorithms highlights the strengths and weaknesses of each approach in handling different graph conditions.

Uploaded by

vehiri3156
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

CMPE232: Data Structures and Algorithms

Lecture Notes
Özgür Özdemir
Istanbul Bilgi University
ozgur.ozdemir@bilgi.edu.tr
Week 06

Shortest Path in General Graphs, Bellman-Ford Algorithm


While Dijkstra’s Algorithm fails in negative-weighted edges and Topological Sorting requires acyclic
graphs, the Bellman-Ford Algorithm provides a solution for general graphs. The algorithm observes
every combination of edges and vertices. Although it is close to the brute-force approach, early stopping
strategies, i.e. terminating the algorithm when updates on distances started vanishing, can be utilized
to perform the algorithm efficiently on large graphs.
Because the Bellman-Ford Algorithm iteratively analyzes every combination of vertices and neigh-
bouring edges, the algorithm runs in O(V.E) time complexity. Unlike removing the vertex from the
queue in Dijkstra’s Algorithm or relaxing the vertex in the DAGSP Algorithm, the shortest path to
the specified target can be obtained only after the distance values become stable; in other words, the
algorithm is completed.

Algorithm 1: Bellman-Ford Algorithm to find shortest paths from the given source vertex
Input: G : edge-weighted graph, s : source vertex, call : number of invoking the function
function BellmanFordSP(G, s):
dist ← initialize a vertices array and assign ∞ to each vertex
edges ← initialize an array of vertices
onQ ← initialize an array of vertices
queue ← initialize an empty regular queue
dist[s] ← 0
queue.enqueue(s)
onQ[s] ← true
while pq ̸= ∅ do
v ← queue.dequeue()
onQ[v] ← f alse
relax(G, v )
end function

function relax(G, v ):
foreach e ∈ G.Adj(v) do
n ← e.other(v)
if dist[n] > dist[v] + e.weight then
dist[n] ← dist[v] + e.weight
edges[n] ← e
if not onQ[n] then
queue.enqueue(n)
onQ[n] ← true
if call = G.V then ▷ to prevent never ending algorithm caused by negative cycles
detectNegativeCycle(G)
call++
end function

1
As given in Algorithm 1, the Bellman-Ford Algorithm may lead to an endless loop if the graph con-
tains negative cycles. The negative cycle refers to a cycle such that one turn causes a negative weight.
Since the distances decrease at each cycle turn, the updates will never be terminated. Therefore, a
control is required to prevent a never-ending algorithm.

2
B C
7 -5 5
5 A B
1 A F -8
2
8 C
D E
1
The shortest path obtained by the Bellman-Ford An example of a negative cycle having a path
Algorithm: A → C → F → E with the distance of A → B → C → A with the distance of -1.
10.

Dijkstra’s Algorithm DAGSP Algorithm Bellman-Ford Algorithm

utilize priority queues utilize Topological Sorting utilize regular queues

fails in negative edge weights fails in cycles fails in negative cycles

O(E.logV ) O(E + V ) O(E.V )

Table: Comparison between algorithms on searching the shortest path.

You might also like