Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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] );
share|improve this question
    
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.:) –  Sangdol Aug 3 '12 at 14:05

1 Answer 1

If I understand you correctly, you're 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.
share|improve this answer
1  
Nah, Floyd-Warshall can compute the paths themselves, same as Djikstra and Bellman-Ford, not just the path lengths. –  Konrad Rudolph Aug 3 '12 at 9:59
    
With modifications, of course. –  Ceasar Bautista Aug 3 '12 at 15:38
2  
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 '12 at 9:59

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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