Changeset 167:7949a29a334e in lemon0.x
 Timestamp:
 03/11/04 13:55:50 (18 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@238
 Location:
 src/work/jacint
 Files:

 1 added
 2 edited
Legend:
 Unmodified
 Added
 Removed

src/work/jacint/dijkstra.cc
r160 r167 22 22 double pre_time=currTime(); 23 23 Dijkstra<ListGraph, int> dijkstra_test(G, s, cap); 24 dijkstra_test.run(); 24 25 double post_time=currTime(); 25 26 26 27 std::cout << "running time: " << post_timepre_time << " sec"<< std::endl; 27 28 29 int hiba=0; 28 30 EachEdgeIt e; 29 30 31 for ( G.getFirst(e) ; G.valid(e); G.next(e) ) { 31 32 NodeIt u=G.tail(e); 32 33 NodeIt v=G.head(e); 33 assert ( dijkstra_test.dist(v)  dijkstra_test.dist(u) <= cap.get(e) ); 34 if ( dijkstra_test.dist(v)  dijkstra_test.dist(u) > cap.get(e) ) { 35 std::cout<<"Hiba: "<<dijkstra_test.dist(v)  dijkstra_test.dist(u)  cap.get(e)<<std::endl; 36 ++hiba; 37 } 34 38 } 39 40 std::cout << "Hibas elek szama: " << hiba << " a " << G.edgeNum() <<"bol."<< std::endl; 35 41 36 42 return 0; 
src/work/jacint/dijkstra.h
r160 r167 3 3 *template <Graph, T, Heap=FibHeap> 4 4 * 5 *6 5 *Constructor: 7 6 * 8 7 *Dijkstra(Graph G, NodeIt s, Graph::EdgeMap<T> length) 9 *10 8 * 11 9 * … … 16 14 * The following function should be used after run() was already run. 17 15 * 18 *19 16 *T dist(NodeIt v) : returns the distance from s to v. 20 17 * It is 0 if v is not reachable from s. 21 *22 18 * 23 19 *EdgeIt pred(NodeIt v) : returns the last edge 24 20 * of a shortest sv path. Returns an invalid iterator 25 21 * if v=s or v is not reachable from s. 26 *27 22 * 28 23 *bool reach(NodeIt v) : true iff v is reachable from s … … 77 72 NodeIt v=heap.top(); 78 73 T oldvalue=heap.get(v); 74 heap.pop(); 79 75 distance.set(v, oldvalue); 80 heap.pop(); 81 76 82 77 OutEdgeIt e; 83 78 for( G.getFirst(e,v); G.valid(e); G.next(e)) { … … 89 84 heap.push(w,oldvalue+length.get(e)); 90 85 predecessor.set(w,e); 91 92 86 } else if ( oldvalue+length.get(e) < heap.get(w) ) { 93 87 predecessor.set(w,e); … … 115 109 return reached.get(v); 116 110 } 117 111 118 112 }; 119 113 120 114 } 121 115
Note: See TracChangeset
for help on using the changeset viewer.