20 /// |
20 /// |
21 /// Dijkstra's algorithm computes shortest paths between two nodes in |
21 /// Dijkstra's algorithm computes shortest paths between two nodes in |
22 /// a graph with edge lengths. Here we only show some of the |
22 /// a graph with edge lengths. Here we only show some of the |
23 /// facilities supplied by our implementation: for the detailed |
23 /// facilities supplied by our implementation: for the detailed |
24 /// documentation of the LEMON Dijkstra class read \ref lemon::Dijkstra "this". |
24 /// documentation of the LEMON Dijkstra class read \ref lemon::Dijkstra "this". |
|
25 /// |
|
26 /// \include dijkstra_demo.cc |
25 |
27 |
26 #include <iostream> |
28 #include <iostream> |
27 |
29 |
28 #include <lemon/list_graph.h> |
30 #include <lemon/list_graph.h> |
29 #include <lemon/dijkstra.h> |
31 #include <lemon/dijkstra.h> |
30 //#include <lemon/graph_writer.h> |
|
31 |
32 |
32 using namespace lemon; |
33 using namespace lemon; |
33 |
34 |
34 |
35 |
35 int main (int, char*[]) |
36 int main (int, char*[]) |
67 len.set(v2_v5, 8); |
68 len.set(v2_v5, 8); |
68 len.set(v3_v5, 5); |
69 len.set(v3_v5, 5); |
69 len.set(v4_t, 8); |
70 len.set(v4_t, 8); |
70 len.set(v5_t, 8); |
71 len.set(v5_t, 8); |
71 |
72 |
72 std::cout << "This program is a simple demo of the LEMON Dijkstra class."<<std::endl; |
73 std::cout << "This program is a simple demo of the LEMON Dijkstra class." |
73 std::cout << "We calculate the shortest path from node s to node t in a graph."<<std::endl; |
74 << std::endl; |
74 std::cout <<std::endl; |
75 std::cout << |
|
76 "We calculate the shortest path from node s to node t in a graph." |
|
77 << std::endl; |
|
78 std::cout << std::endl; |
75 |
79 |
76 |
80 |
77 std::cout << "The id of s is " << g.id(s)<< ", the id of t is " << g.id(t)<<"."<<std::endl; |
81 std::cout << "The id of s is " << g.id(s)<< ", the id of t is " |
|
82 << g.id(t) << "." << std::endl; |
78 |
83 |
79 std::cout << "Dijkstra algorithm demo..." << std::endl; |
84 std::cout << "Dijkstra algorithm demo..." << std::endl; |
80 |
|
81 |
85 |
82 Dijkstra<Graph, LengthMap> dijkstra_test(g,len); |
86 Dijkstra<Graph, LengthMap> dijkstra_test(g,len); |
83 |
87 |
84 dijkstra_test.run(s); |
88 dijkstra_test.run(s); |
|
89 |
|
90 std::cout << "The distance of node t from node s: " |
|
91 << dijkstra_test.dist(t) << std::endl; |
85 |
92 |
|
93 std::cout << "The shortest path from s to t goes through the following " |
|
94 << "nodes (the first one is t, the last one is s): " |
|
95 << std::endl; |
|
96 |
|
97 for (Node v=t;v != s; v=dijkstra_test.predNode(v)) { |
|
98 std::cout << g.id(v) << "<-"; |
|
99 } |
86 |
100 |
87 std::cout << "The distance of node t from node s: " << dijkstra_test.dist(t)<<std::endl; |
|
88 |
|
89 std::cout << "The shortest path from s to t goes through the following nodes (the first one is t, the last one is s): "<<std::endl; |
|
90 |
|
91 for (Node v=t;v != s; v=dijkstra_test.predNode(v)){ |
|
92 std::cout << g.id(v) << "<-"; |
|
93 } |
|
94 std::cout << g.id(s) << std::endl; |
101 std::cout << g.id(s) << std::endl; |
95 |
102 |
96 |
|
97 return 0; |
103 return 0; |
98 } |
104 } |
99 |
|
100 |
|
101 |
|
102 |
|
103 |
|
104 |
|
105 |
|
106 |
|
107 |
|