# Am I right about the differences between Floyd-Warshall, Dijkstra's and Bellman-Ford algorithms?

I've been studying the three and I'm stating my inferences from them below. Could someone tell me if I have understood them accurately enough or not? Thank you.

1. Dijkstra's algorithm is used only when you have a single source and you want to know the smallest path from one node to another, but fails in cases like this

2. Floyd-Warshall's algorithm is used when any of all the nodes can be a source, so you want the shortest distance to reach any destination node from any source node. This only fails when there are negative cycles

(this is the most important one. I mean, this is the one I'm least sure about:)

3.Bellman-Ford is used like Dijkstra's, when there is only one source. This can handle negative weights and its working is the same as Floyd-Warshall's except for one source, right?

If you need to have a look, the corresponding algorithms are (courtesy Wikipedia):

Bellman-Ford:

`````` procedure BellmanFord(list vertices, list edges, vertex source)
// This implementation takes in a graph, represented as lists of vertices
// and edges, and modifies the vertices so that their distance and
// predecessor attributes store the shortest paths.

// Step 1: initialize graph
for each vertex v in vertices:
if v is source then v.distance := 0
else v.distance := infinity
v.predecessor := null

// Step 2: relax edges repeatedly
for i from 1 to size(vertices)-1:
for each edge uv in edges: // uv is the edge from u to v
u := uv.source
v := uv.destination
if u.distance + uv.weight < v.distance:
v.distance := u.distance + uv.weight
v.predecessor := u

// Step 3: check for negative-weight cycles
for each edge uv in edges:
u := uv.source
v := uv.destination
if u.distance + uv.weight < v.distance:
error "Graph contains a negative-weight cycle"
``````

Dijkstra:

`````` 1  function Dijkstra(Graph, source):
2      for each vertex v in Graph:                                // Initializations
3          dist[v] := infinity ;                                  // Unknown distance function from
4                                                                 // source to v
5          previous[v] := undefined ;                             // Previous node in optimal path
6                                                                 // from source
7
8      dist[source] := 0 ;                                        // Distance from source to source
9      Q := the set of all nodes in Graph ;                       // All nodes in the graph are
10                                                                 // unoptimized - thus are in Q
11      while Q is not empty:                                      // The main loop
12          u := vertex in Q with smallest distance in dist[] ;    // Start node in first case
13          if dist[u] = infinity:
14              break ;                                            // all remaining vertices are
15                                                                 // inaccessible from source
16
17          remove u from Q ;
18          for each neighbor v of u:                              // where v has not yet been
19                                                                                 removed from Q.
20              alt := dist[u] + dist_between(u, v) ;
21              if alt < dist[v]:                                  // Relax (u,v,a)
22                  dist[v] := alt ;
23                  previous[v] := u ;
24                  decrease-key v in Q;                           // Reorder v in the Queue
25      return dist;
``````

Floyd-Warshall:

`````` 1 /* Assume a function edgeCost(i,j) which returns the cost of the edge from i to j
2    (infinity if there is none).
3    Also assume that n is the number of vertices and edgeCost(i,i) = 0
4 */
5
6 int path[][];
7 /* A 2-dimensional matrix. At each step in the algorithm, path[i][j] is the shortest path
8    from i to j using intermediate vertices (1..k−1).  Each path[i][j] is initialized to
9    edgeCost(i,j).
10 */
11
12 procedure FloydWarshall ()
13    for k := 1 to n
14       for i := 1 to n
15          for j := 1 to n
16             path[i][j] = min ( path[i][j], path[i][k]+path[k][j] );
``````
• I'm pretty sure Dijkstra's algorithm can handle negative-weight nodes. If there are negative-weight cycles the shortest path is undefined, regardless of the algorithm. – kevin cline Jul 28 '12 at 22:32
• @kevincline: Wikipedia doesn't support your claim (I'm not claiming wikipedia is right though, and I have my AlgTheory book a few hundred miles away) However, in real-life time-based or speed-based routing problems there are no negative edges, so I usually do Dijsktra or Floyd, depending on the need. As far as I remember, most real-life cartographical routing algos are based on modernized version of Dijsktra's, but I just remember it from some scientific papers I've read at my previous workplace. – Aadaam Jul 29 '12 at 1:18
• @Aadaam: I am wrong. Dijkstra exploits non-negativity to avoid visiting every edge. – kevin cline Jul 29 '12 at 17:56
• Yes, you understood correctly.:) – Sanghyun Lee Aug 3 '12 at 14:05