2
$\begingroup$

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!

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – matteodv Jun 8 '17 at 18:00
  • $\begingroup$ Yes, that's the inescapable conclusion. $\endgroup$ – Yuval Filmus Jun 8 '17 at 19:08
  • $\begingroup$ @matteodv Note that the twoa algorithms solve different problems! $\endgroup$ – Raphael Jun 8 '17 at 19:53
  • $\begingroup$ @Raphael can you explain a bit more? Thanks! $\endgroup$ – matteodv Jun 8 '17 at 20:05
  • 2
    $\begingroup$ @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)! $\endgroup$ – Raphael Jun 9 '17 at 4:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.