# Retrieve shortest path between two nodes using Bellman-Ford-Moore algorithm sequentially

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

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!

The correctness proof of the Bellmanâ€“Ford algorithm relies on the following lemma (compare Wikipedia):

After $i$ iterations, $d[v]$ is at most the distance of the shortest path of length $i$ from the source vertex to $v$.

Indeed, if we perform all updates at a specific iteration in parallel, then $d[v]$ equals the distance of the shortest path of length $i$. When we perform the updates sequentially we might get lucky, and this depends on the order of vertices in the path.

This shows that in general you cannot stop Bellmanâ€“Ford early in the way you envision.

• Thank you so much for your answer! So the execution of Dijkstra algorithm can be stopped before completion while Bellman-Ford has to finish analyzing the whole graph (assuming a sequential execution), right? – matteodv Jun 8 '17 at 18:00
• Yes, that's the inescapable conclusion. – Yuval Filmus Jun 8 '17 at 19:08
• @matteodv Note that the twoa algorithms solve different problems! – Raphael Jun 8 '17 at 19:53
• @Raphael can you explain a bit more? Thanks! – matteodv Jun 8 '17 at 20:05
• @matteodv Bellman-Ford can handle negative weights, Dijkstra does not. So the former having to investigate the whole graph is not a flaw: it's actually necessary, since with negative weights an edge-longer graph can be weight-shorter. Dijkstra, on the other hand, heavily relies on the fact that edge-longer paths can never be weight-shorter (if there are no negative weights)! – Raphael Jun 9 '17 at 4:46