This is my first question here and I hope you can help mt clarifying a doubt.
Basically, I'm studying shortest path algorithms, for instance Dijkstra, Bellman-Ford-Moore, and I came up with a doubt.
From what I understood, given a node of a graph, these algorithms calculate all the shortest paths to the other nodes. So, if I block the execution when a specific condition is met, I can get just the shortest path between two nodes.
I don't have problems with Dijkstra but I can't prove this assumption with Bellman-Ford-Moore algorithm. Consider this example:
G = (V,E)
directed graph where V = {1,2,3,4,5,6}
, E = {(1,3),(1,2),(3,2),(3,4),(2,5),(5,4),(4,6),(5,6)}
and each arch has the following costs
, respectively: 2,1,3,3,1,2,2,5
.
The shortest path between node 1
and node 4
is: 1 -> 2 -> 5 -> 4
whose cost is 4.
If I try to execute BFM on this graph, assuming nodes are added in the queue with this order: 1,3,2,4,5
; the result is not what I'm expecting because the algorithm terminates returning the path 1 -> 3 -> 4
, whose cost is 5.
This is the pseudocode I'm using:
bfm(GRAPH G, NODE r, NODE s, integer[] T)
integer[] d <- new integer[1...G.n]
boolean[] b <- new integer[1...G.n]
foreach u in G.V() - {r} do
T[u] <- nil
d[u] <- inf
b[u] <- false
T[r] <- nil
d[r] <- 0
b[r] <- true
QUEUE S <- new Queue()
Q.enqueue(r)
while not S.isEmpty() do
NODE u <- S.dequeue()
b[u] <- false
if u = s then return
foreach v in G.adj(u) do
if d[u] + w(u,v) < d[v] then
if not b[v] then
S.enqueue(v)
b[v] <- true
T[v] <- u
d[v] <- d[u] + w(u,v)
d
is a vector to track distances, b
is a vector to track which node is currently in the queue, T
is a vector of fathers, G.adj(u)
returns all nodes adjacent to node u
and w(u,v)
is the cost function.
Since Dijkstra and BFM algorithms are quite similar, I thought my assumption would be valid for both of them but it seems that I'm wrong. Can you please help me understanding if and how I can use BFM to get the shortest path between two specific nodes?
Thank you so much!