equal
deleted
inserted
replaced
71 Dijkstra<Graph, LengthMap> |
71 Dijkstra<Graph, LengthMap> |
72 dijkstra_test(G, cap); |
72 dijkstra_test(G, cap); |
73 dijkstra_test.run(s); |
73 dijkstra_test.run(s); |
74 |
74 |
75 check(dijkstra_test.dist(t)==13,"Dijkstra found a wrong path."); |
75 check(dijkstra_test.dist(t)==13,"Dijkstra found a wrong path."); |
76 |
76 |
|
77 |
|
78 for(EdgeIt e(G); G.valid(e); G.next(e)) { |
|
79 Node u=G.tail(e); |
|
80 Node v=G.head(e); |
|
81 check( !dijkstra_test.reached(u) || |
|
82 (dijkstra_test.dist(v) - dijkstra_test.dist(u) <= cap[e]), |
|
83 "dist(head)-dist(tail)- edge_length= " |
|
84 << dijkstra_test.dist(v) - dijkstra_test.dist(u) |
|
85 - cap[e]); |
|
86 } |
|
87 |
|
88 ///\bug This works only for integer lengths |
|
89 for(NodeIt v(G); G.valid(v); G.next(v)) |
|
90 if ( dijkstra_test.reached(v) ) { |
|
91 Edge e=dijkstra_test.pred(v); |
|
92 Node u=G.tail(e); |
|
93 check(dijkstra_test.dist(v) - dijkstra_test.dist(u) == cap[e], |
|
94 "Bad shortest path tree edge! Difference: " |
|
95 << std::abs(dijkstra_test.dist(v) - dijkstra_test.dist(u) |
|
96 - cap[e])); |
|
97 } |
77 } |
98 } |