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

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

数值算法/人工智能

开发平台：

MultiPlatform

main.c：源码内容
  2. /* This file has been automatically generated from "r_heap.w"
  3.    by CTANGLE (Version 3.1 [km2c]) */
  8. #include "r_heap.h"
  9. #include <LEDA/random.h>
  10. #include <LEDA/p_queue.h>
  11. #include <LEDA/_p_queue.h>
  12. #include <LEDA/graph.h>
  13. #include <LEDA/graph_alg.h>
  14. #include <fstream.h>
  15. #include <string.h>
  16. #include <math.h>
  21. void dijkstra(graph &G,
  22.    node s,
  23.    edge_array <int >&cost,
  24.    node_array <int >&dist,
  25.    node_array <edge >&pred,
  26.    p_queue < int, node >&PQ)
  27. {
  29.   node_array <pq_item >I(G);
  30.   node v;
  32.   forall_nodes (v, G) {
  33.     pred[v] = nil;
  34.     dist[v] = MAXINT;
  35.   }
  37.   dist[s] = 0;
  38.   I[s] = PQ.insert(0, s);
  40.   while (!PQ.empty()) {
  42.     pq_item it = PQ.find_min();
  43.     node u = PQ.inf(it);
  44.     int du = dist[u];
  45.     edge e;
  46.     forall_adj_edges (e, u) {
  47.       v = G.target(e);
  48.       int c = du + cost[e];
  49.       if (c < dist[v]) {
  50. if (dist[v] == MAXINT)
  51.   I[v] = PQ.insert(c, v);
  52. else
  53.   PQ.decrease_p(I[v], c);
  54. dist[v] = c;
  55. pred[v] = e;
  56.       }
  57.     }
  58.     PQ.del_item(it);
  59.   }
  60. }
  65. int main(void)
  66. {
  67.   GRAPH <int, int >G;
  68.   int n = read_int("# nodes = ");
  69.   int m = read_int("# edges = ");
  70.   random_graph(G, n, m);
  71.   edge_array <int >cost(G);
  72.   node_array <int >dist(G);
  73.   node_array <edge >pred(G);
  74.   int M = read_int("max edge cost = ");
  75.   node s = G.choose_node();
  76.   edge e;
  77.   forall_edges (e, G)
  78.     G[e] = cost[e] = rand_int(0, M);
  79.   p_queue < int, node >*PQ[2];
  80.   PQ[0] = new _p_queue < int, node, f_heap >;
  81.   PQ[1] = new _p_queue < int, node, r_heap > (M);
  82.   float T = used_time();
  83.   float t_f = 0.0, t_r = 0.0;
  84.   dijkstra(G, s, cost, dist, pred, *(PQ[0]));
  85.   t_f = used_time(T);
  86.   dijkstra(G, s, cost, dist, pred, *(PQ[1]));
  87.   t_r = used_time(T);
  88.   cout << string ("f_heap: %6.2f sec, r_heap: %6.2f secn", t_f, t_r);
  89. }