equal
deleted
inserted
replaced
16 * |
16 * |
17 */ |
17 */ |
18 |
18 |
19 ///\ingroup demos |
19 ///\ingroup demos |
20 ///\file |
20 ///\file |
21 ///\brief Demonstrating the usage of LEMON's Dijkstra algorithm |
21 ///\brief Demonstrating the usage of LEMON's algorithm for solving the |
|
22 /// Constrained shortest Path Problem |
22 /// |
23 /// |
23 /// Dijkstra's algorithm computes shortest paths between two nodes in |
24 /// \include csp_demo.cc |
24 /// a graph with edge lengths. Here we only show some of the |
|
25 /// facilities supplied by our implementation: for the detailed |
|
26 /// documentation of the LEMON Dijkstra class read \ref lemon::Dijkstra "this". |
|
27 /// |
|
28 /// \include dijkstra_demo.cc |
|
29 |
25 |
30 #include <iostream> |
26 #include <iostream> |
31 #include <lemon/list_graph.h> |
27 #include <lemon/list_graph.h> |
32 #include <lemon/csp.h> |
28 #include <lemon/csp.h> |
33 #include <lemon/random.h> |
29 #include <lemon/random.h> |
64 cost[e]=0.01+rnd(.99); |
60 cost[e]=0.01+rnd(.99); |
65 delay[e]=0.01+rnd(.99); |
61 delay[e]=0.01+rnd(.99); |
66 } |
62 } |
67 |
63 |
68 ConstrainedShortestPath<Graph,LengthMap,LengthMap> csp(g,cost,delay); |
64 ConstrainedShortestPath<Graph,LengthMap,LengthMap> csp(g,cost,delay); |
69 for(double d=0;d<2;d+=.01) |
65 for(double d=0;d<2;d+=.001) |
70 { |
66 { |
71 double lo_bo; |
67 double lo_bo; |
72 std::cout << d << ": "; |
68 std::cout << d << ": "; |
73 SimplePath<Graph> r = csp.larac(nodes[0],nodes[1],d,lo_bo); |
69 SimplePath<Graph> r = csp.larac(nodes[0],nodes[1],d,lo_bo); |
74 if(r.empty()) std::cout << "INFEASIBLE\n"; |
70 if(r.empty()) std::cout << "INFEASIBLE\n"; |