开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > 数值算法/人工智能 > 查看源码
_dijkstra.c
资源名称：leda.tar.gz　[点击查看]
上传用户：gzelex
上传日期：2007-01-07
资源大小：707k
文件大小：3k
源码类别：

数值算法/人工智能

开发平台：

MultiPlatform

_dijkstra.c：源码内容
  1. /*******************************************************************************
  2. +
  3. +  LEDA-R  3.2.3
  4. +
  5. +  _dijkstra.c
  6. +
  7. +  Copyright (c) 1995  by  Max-Planck-Institut fuer Informatik
  8. +  Im Stadtwald, 66123 Saarbruecken, Germany     
  9. +  All rights reserved.
  10. + 
  11. *******************************************************************************/
  14. /*******************************************************************************
  15. *                                                                              *
  16. *  DIJKSTRA  (single source shortest paths)                                    *
  17. *                                                                              *
  18. *******************************************************************************/
  21. #include <LEDA/graph_alg.h>
  22. #include <LEDA/node_pq.h>
  25. void DIJKSTRA(const graph& G, node s, const edge_array<num_type>& cost,
  26.                                             node_array<num_type>& dist,
  27.                                             node_array<edge>& pred )
  28. { /* 
  29.      computes single source shortest paths from node s for 
  30.      a non-negative network (G,cost), computes for all nodes v:
  31.      a) dist[v] = cost of shortest path from s to v
  32.      b) pred[v] = predecessor edge of v in shortest paths tree
  33.   */
  35.   node_pq<num_type>  PQ(G);
  36.   node v;                                                                    
  37.   edge e;                                                                      
  38.                                                                                
  39.   forall_nodes(v,G)                                                            
  40.   { pred[v] = nil;                                                             
  41.     dist[v] = max_num;                                                      
  42.    }                                                                         
  44.   dist[s] = 0;
  45.   PQ.insert(s,0);
  46.                                                                                
  47.   while (! PQ.empty())
  48.   { node u = PQ.del_min();
  49.     num_type du = dist[u];
  50.     forall_adj_edges(e,u)                                                    
  51.     { v = target(e);                                                      
  52.       num_type c = du + cost[e];                                              
  53.       if (c < dist[v])                                                    
  54.       { if (dist[v] == max_num) 
  55.            PQ.insert(v,c);
  56.         else 
  57.            PQ.decrease_p(v,c);
  58.         dist[v] = c;                                                     
  59.         pred[v] = e;                                                     
  60.        }                                                                 
  61.      }                                                                    
  62.    } 
  63. }