CODEWITHSUNDEEP
algorithmgraphbellman-ford
goerlibe
goerlibe

Reputation: 120

Is the result of Bellman-Ford "all pairs" or "from one node" shortest paths? / Is there an all-pairs Bellman-Ford version?

I am recently learning about graph algorithms and at my university we were taught, that the result of Bellman-Ford is a table of distances from all nodes to all other nodes (all-pairs shortest paths). However I did not understand how this is achieved by the algorithm and tried to understand it by watching YouTube videos and looking up definitions in Wikipedia and so forth...

Now here comes the problem:
I could not find resources that described the algorithm in a way that the result would be the all pairs shortest paths table, but only "from one node to all other nodes".

Can the Bellman-Ford algorithm be tweaked to achieve the all pairs shortest paths table or is my university-lecturer completely wrong about this? (He did explain some algorithm that delivered all pairs shortest paths and he called it Bellman-Ford, however I think this can not be Bellman Ford)

EDIT: I absolutely understand the Bellman-Ford algorithm for the Problem "shortest path from one node to all other nodes".
I also understand most of the algorithm that was taught at my university for "all pairs shortest paths".
I am just very confused since the algorithm at my university was also called "Bellman-Ford".
If you speak German: Here is a video where the university lecturer talks about his "Bellman-Ford" (which I think is not actually Bellman-Ford):
https://www.youtube.com/watch?v=3_zqU5GWo4w&t=715s

Upvotes: 1

Views: 4319

Answers (3)

goerlibe
goerlibe

Reputation: 120

I asked in our university forum and got the following answer:

Bellman-Ford is originally "from one node". The invariant (idea under the hood of the algorithm) however does not change when applying the original Bellman-Ford algorithm to every node of the Graph.

Complexity of the original Bellman-Ford is O(V^3) and if started from every Node it would be O(V^4). However there is a trick that one can use because the findings during the algorithm resemble matrix multiplications of the input matrix (containing direct path lengths) with itself. Because this is a mathematical ring one can cheat and simply calculate matrix^2, matrix^4, matrix^8 and so on (This is the part I did not completely understand though) and one can achieve O(V^3 * log V).

He called this algorithm Bellman-Ford as well, because the invariant/ idea behind the algorithm is still the same.

German answer in our public university forum

Upvotes: 1

someone12321
someone12321

Reputation: 755

Bellman Ford is algorithm for finding shortest path from given start node to any other node in the graph.

Using Bellman Ford we can generate all pairs shortest paths if we run the bellman ford algorithm from each node and then get the shortest paths to all others, but the worse case time complexity of this algorithm will be O(V * V * E) and if we have complete graph this complexity will be O (V^4), where V is the number of vertexes (nodes) in the graph and E is the number of edges in the graph.

There is better algorithm for finding all pairs shortest paths which works in O(V^3) time complexity. That is the Floyd Warshall algorithm.

Here you can read more about it: https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm

Upvotes: 5

Pushan Gupta
Pushan Gupta

Reputation: 3825

The aim of the algorithm is to find the shortest path from the starting point to the ending point.

To do that, it finds the shortest distance from the all points to every other point and then selects the path that leads to the solution and also adds up to the shortest.

To begin with, it starts with the starting point (A). Sets every point's cost to infinity.

Now it sees all the possible directions from A. And A's initial cost is set to zero.

Imagine it needs to travel to only B. One there might be a straight path that connects B to A and its cost is say, 10.

But there is also a path via C. From A to C it takes say cost 5 and from C to B it takes cost only 2. This means that there are two possible paths from A to B. One that has cost 10 and the other 5+2 i.e. 7 . So it shall update the cost of reaching B from A to 7 not 10 and hence the path shall be selected.

You can imagine this same situation but with many more points. It shall search from starting point to reach the end point traversing all the possible paths and updating/not updating the cost as and when needed. In the end it shall look for all the paths and select the one that has the smallest cost.

Now here comes the problem: a I could not find resources that described the algorithm in a way that the result would be the all pairs shortest paths table, but only "from one node to all other nodes".

To understand that, imagine we have to reach A to D.

The individual cost of moving from one point to another is listed below

  • A to B :15

  • A to C :10

  • B to C :3

  • B to D :5

  • C to D :15

Initially set all points to infinity except A to zero.

First,

A->B : Cost=15(Update B's cost to 15)

A->C : Cost=10(Update C's cost to 10)

B->C : Cost=18(B's cost plus B->C alone cost, so do not update as C's cost as is already smaller than this)

C->B : Cost=13(C's cost plus C->B alone cost, update B's cost to 13 as this is smaller than 15)

B->D : Cost=18(B's new cost plus B->D cost alone, update D's cost as this smaller than infinity)

C->D : Cost=25(C's cost plus C->D cost alone, do not update D)

So the path that the algorithm chooses is the one that lead to D with the cost of 18 which comes out to be the smallest cost!

     B  
  /  |  \ 
A    |   D
  \  | /
     C

A->C->B->D Cost:18

Now you may read this link for better understanding. And things should be pretty clear.

Upvotes: 1

Related Questions