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

Question

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!

Answer 1

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.