_dijkstra.c

数据类型和算法库LEDA 数据类型和算法库LEDA

/*******************************************************************************
+
+  LEDA  3.0
+
+
+  _dijkstra.c
+
+
+  Copyright (c) 1992  by  Max-Planck-Institut fuer Informatik
+  Im Stadtwald, 6600 Saarbruecken, FRG     
+  All rights reserved.
+ 
*******************************************************************************/



/*******************************************************************************
*                                                                              *
*  DIJKSTRA  (single source shortest paths)                                    *
*                                                                              *
*******************************************************************************/


#include <LEDA/graph_alg.h>
#include <LEDA/prio.h>


#if defined(REAL_NUMBERS)
typedef double num_type;
typedef node_array<double> num_node_array;
typedef edge_array<double> num_edge_array;
#else
typedef int num_type;
typedef node_array<int> num_node_array;
typedef edge_array<int> num_edge_array;
#endif



void DIJKSTRA(const graph& G, node s, const num_edge_array& cost,
                                            num_node_array& dist,
                                            node_array<edge>& pred )
{ /* 
     computes single source shortest paths from node s for 
     a non-negative network (G,cost), computes for all nodes v:
     a) dist[v] = cost of shortest path from s to v
     b) pred[v] = predecessor edge of v in shortest paths tree
  */

  priority_queue<node,num_type> PQ;
  node_array<pq_item> I(G);
  node v;                                                                    
  edge e;                                                                      
                                                                               
  forall_nodes(v,G)                                                            
  { pred[v] = nil;                                                             
    dist[v] = MAXINT;                                                      
   }                                                                         

  dist[s] = 0;
  I[s] = PQ.insert(s,0);
                                                                               
  while (! PQ.empty())
  { node u = PQ.del_min();
    num_type du = dist[u];
    forall_adj_edges(e,u)                                                    
    { v = target(e);                                                      
      num_type c = du + cost[e];                                              
      if (c < dist[v])                                                    
      { if (dist[v] == MAXINT) 
           I[v] = PQ.insert(v,c);
        else 
           PQ.decrease_inf(I[v],c);
        dist[v] = c;                                                     
        pred[v] = e;                                                     
       }                                                                 
     }                                                                    
   } 
}