home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / prog / graph / short.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-11-15  |  2.0 KB  |  110 lines
  1. #include <LEDA/graph.h>
  2. #include <LEDA/graph_alg.h>
  3.  
  4. declare2(GRAPH,int,int);
  5.  
  6. main()
  7. {
  8.  
  9. GRAPH(int,int) G;
  10. node s,v,w;
  11. edge e;
  12.  
  13. int n = read_int("# nodes = ");
  14. int m = read_int("# edges = ");
  15.  
  16.  
  17. edge_array(int)  cost(G,m,0);
  18. node_array(int)  dist(G,n,0);
  19. node_array(int)  dist2(G,n,0);
  20.  
  21. edge_array(real) cost1(G,m,0);
  22. node_array(real) dist1(G,n,0);
  23. node_array(real) dist3(G,n,0);
  24.  
  25. node_array(edge) pred(G,n,nil);
  26.  
  27. random_graph(G,n,m);
  28.  
  29. int a = read_int("a = ");
  30. int b = read_int("b = ");
  31.  
  32. init_random();
  33. forall_edges(e,G) cost1[e] = cost[e] = G[e] = random(a,b);
  34.  
  35.  
  36.  
  37. s = G.first_node();
  38.  
  39. float T = used_time();
  40.  
  41. cout << "DIJKSTRA (int)      ";
  42. cout.flush();
  43. DIJKSTRA(G,s,cost,dist,pred);
  44. cout << form("%6.2f sec  \n",used_time(T));
  45.  
  46. cout << "DIJKSTRA (real)     ";
  47. cout.flush();
  48. DIJKSTRA(G,s,cost1,dist1,pred);
  49. cout << form("%6.2f sec  \n",used_time(T));
  50.  
  51. cout << "BELLMAN_FORD (int)  ";
  52. cout.flush();
  53. BELLMAN_FORD(G,s,cost,dist2,pred);
  54. cout << form("%6.2f sec  \n",used_time(T));
  55.  
  56.  
  57. cout << "BELLMAN_FORD (real) ";
  58. cout.flush();
  59. BELLMAN_FORD(G,s,cost1,dist3,pred);
  60. cout << form("%6.2f sec  \n",used_time(T));
  61.  
  62. if (Yes("Ausgabe ? "))
  63.  { forall_nodes(v,G)
  64.    { G.print_node(v);
  65.      cout << form(" %6d %6.2f %6d %6.2f\n",dist[v],~dist1[v],dist2[v],~dist3[v]);
  66.     }
  67.    newline;
  68.   }
  69.  
  70.  
  71. if (Yes("all pairs shortest paths (int) ? "))
  72. { 
  73.   node_matrix(int) Mi(G);
  74.  
  75.   used_time(T);
  76.   cout << "ALL PAIRS SHORTEST PATHS (int) ";
  77.   cout.flush();
  78.   ALL_PAIRS_SHORTEST_PATHS(G,cost,Mi);
  79.   cout << form("%.2f sec\n",used_time(T));
  80.   
  81.   if (Yes("Ausgabe ? "))
  82.     forall_nodes(v,G)
  83.      { forall_nodes(w,G) cout << form("%6d ",Mi(v,w));
  84.        newline;
  85.        }
  86.   newline;
  87. }
  88.  
  89.  
  90. if (Yes("all pairs shortest paths (real) ? "))
  91. { 
  92.   node_matrix(real) Mr(G);
  93.  
  94.   used_time(T);
  95.   cout << "ALL PAIRS SHORTEST PATHS (real)  ";
  96.   cout.flush();
  97.   ALL_PAIRS_SHORTEST_PATHS(G,cost1,Mr);
  98.   cout << form("%.2f sec\n",used_time(T));
  99.   
  100.   if (Yes("Ausgabe ? "))
  101.     forall_nodes(v,G)
  102.      { forall_nodes(w,G) cout << form("%6.2f ",~Mr(v,w));
  103.        newline;
  104.        }
  105.   newline;
  106.  
  107.  }
  108.  
  109. }
  110.