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

 1 edited
Legend:
 Unmodified
 Added
 Removed

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.