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

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

数值算法/人工智能

开发平台：

MultiPlatform

neg_cycle.c：源码内容
  1. #include <LEDA/graph.h>
  2. #include <LEDA/graph_alg.h>
  5. main()
  6. {
  8. GRAPH<int,int> G;
  9. node u;
  10. edge e;
  12. test_graph(G);
  14. edge_array<int>  cost(G,0);
  15. node_array<int>  dist(G,0);
  16. node_array<edge> pred(G,nil);
  17. node_array<int>  label(G,0);
  19. int mi = read_int("min cost = ");
  20. int ma = read_int("max cost = ");
  22. forall_edges(e,G) cost[e] = G[e] = rand_int(mi,ma);
  24. node s = G.first_node();
  26. float T = used_time();
  28. cout << "BELLMAN_FORD <int>  " << flush;
  29. bool b = BELLMAN_FORD(G,s,cost,dist,pred);
  30. cout << string("%6.2f sec  ",used_time(T)) << endl;
  31. newline;
  34. if (b == false)
  35.   { cout << "Negative cycle:" << endl;
  36.     int count = 1;
  37.     forall_nodes(u,G)
  38.     { if (label[u] == 0)
  39.        { while (label[u]==0)
  40.          { label[u]=count;
  41.            u=source(pred[u]);
  42.           }
  43.          if (label[u] == count)  // cycle found
  44.          { list<edge> cycle;
  45.            for(e=pred[u]; source(e)!=u; e=pred[source(e)]) cycle.push(e);
  46.            cycle.push(e);
  47.            forall(e,cycle)
  48.            { G.print_edge(e);
  49.              newline;
  50.             }
  51.            newline;
  52.           }
  53.         }
  54.       count++;
  55.      }
  56.    }
  57. else
  58.   cout << "No negativ cycle found" << endl;
  60. return 0;
  62. }