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):


 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"


 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
 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
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;


 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 */
 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 */
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. Jul 28, 2012 at 22:32
  • 1
    @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, 2012 at 1:18
  • @Aadaam: I am wrong. Dijkstra exploits non-negativity to avoid visiting every edge. Jul 29, 2012 at 17:56
  • Yes, you understood correctly.:) Aug 3, 2012 at 14:05

1 Answer 1


If I understand you correctly, your understanding is correct.

  • Djikstra's finds the smallest cost path from a source node to every other node in the graph, except if there is a negative weight edge. (Dijkstra's can be transformed easily into the A* algorithm by just changing it to stop once its found the target node and adding heuristics.)
  • Bellman-Ford does the same as Dijkstra's, but is slower. But it can handle negative weight edges.
  • Floyd-Warshall finds the cost of the smallest cost path from each node to every other node. (It returns a numeric matrix.) It is far slower than either Djikstra's or Bellman-Ford. Unlike what you wrote, it does not fail when a negative cycle occurs, it just reports a meaningless negative number for the cost of some node to itself.
  • 1
    Nah, Floyd-Warshall can compute the paths themselves, same as Djikstra and Bellman-Ford, not just the path lengths. Aug 3, 2012 at 9:59
  • With modifications, of course.
    – Ceasar
    Aug 3, 2012 at 15:38
  • 3
    I would still consider the first one to be Dijkstra's if it were stopped at a target node, but didn't use heuristics.
    – Eliot Ball
    Sep 2, 2012 at 9:59
  • 1
    @CSA - Floyd Warshall is O(n^3), so around 10^300 operations would be required for such a large graph. Assuming each operation takes Planck time, by the time the calculation has finished all of the protons in the regular matter in the universe will have decayed, and only supermassive black holes will be left. I believe it may be possible to parallelize the inner loop. If this is true, you may be lucky enough to finish before all the black holes that started with the mass of the sun have evaporated.
    – Jules
    Apr 7, 2017 at 22:12
  • 1
    (Assuming you can build a processing node using less than one atom per process, and can use all of the atoms in the observable universe, that is... but then you probably need all of those to store your data to start with)
    – Jules
    Apr 7, 2017 at 22:17

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.