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

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

数值算法/人工智能

开发平台：

MultiPlatform

_d.c：源码内容
  1. /*******************************************************************************
  2. +
  3. +  LEDA-R  3.2.3
  4. +
  5. +  _d.c
  6. +
  7. +  Copyright (c) 1995  by  Max-Planck-Institut fuer Informatik
  8. +  Im Stadtwald, 66123 Saarbruecken, Germany     
  9. +  All rights reserved.
  10. + 
  11. *******************************************************************************/
  13. #include <LEDA/graph.h>
  14. #include <LEDA/p_queue.h>
  17. void DIJKSTRA(graph& G, node s, 
  18.               edge_array<int>&  cost, 
  19.               node_array<int>&  dist,
  20.               node_array<edge>& pred,
  21.               p_queue<int,node>&   PQ)
  22. {
  23.   node_array<pq_item> I(G);
  24.   node v;
  25.                                                                                
  26.   forall_nodes(v,G)
  27.   { pred[v] = nil;
  28.     dist[v] = MAXINT;
  29.    }
  31.   dist[s] = 0;
  32.   I[s] = PQ.insert(0,s);
  34.   while (! PQ.empty())
  35.   { pq_item it = PQ.find_min();
  36.     node u = PQ.inf(it);
  37.     int du = dist[u];
  38.     edge e;
  39.     forall_adj_edges(e,u)
  40.     { v = G.target(e);
  41.       int c = du + cost[e];
  42.       if (c < dist[v])
  43.       { if (dist[v] == MAXINT)
  44.           I[v] = PQ.insert(c,v);
  45.         else
  46.           PQ.decrease_p(I[v],c);
  47.         dist[v] = c;
  48.         pred[v] = e;
  49.        }                                                                 
  50.      }
  51.     PQ.del_item(it);
  52.    }
  53. }
  56. void DIJKSTRA(graph& G, node s, 
  57.               edge_array<int>&  cost, 
  58.               node_array<int>&  dist,
  59.               node_array<edge>& pred)
  60. {
  61.   p_queue<int,node>  PQ;
  63.   DIJKSTRA(G,s,cost,dist,pred,PQ);
  65.  }