Changeset 1723:fb4f801dd692 in lemon-0.x for lemon/belmann_ford.h
- Timestamp:
- 10/14/05 12:53:51 (19 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2250
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/belmann_ford.h
r1710 r1723 145 145 /// 146 146 /// \ingroup flowalgs 147 /// This class provides an efficient implementation of \c Belmann Ford147 /// This class provides an efficient implementation of \c Belmann-Ford 148 148 /// algorithm. The edge lengths are passed to the algorithm using a 149 149 /// \ref concept::ReadMap "ReadMap", so it is easy to change it to any 150 150 /// kind of length. 151 /// 152 /// The Belmann-Ford algorithm solves the shortest path from one node 153 /// problem when the edges can have negative length but the graph should 154 /// not contain circle with negative sum of length. If we can assume 155 /// that all edge is non-negative in the graph then the dijkstra algorithm 156 /// should be used rather. 157 /// 158 /// The complexity of the algorithm is O(n * e). 151 159 /// 152 160 /// The type of the length is determined by the … … 403 411 /// - The distance of each node from the root(s). 404 412 void start() { 405 bool ready = false;406 while (!ready) {407 ready = true;413 int num = countNodes(*graph) - 1; 414 for (int i = 0; i < num; ++i) { 415 bool ready = true; 408 416 for (EdgeIt it(*graph); it != INVALID; ++it) { 409 417 Node source = graph->source(it); … … 417 425 } 418 426 } 419 } 427 if (ready) return; 428 } 429 } 430 431 /// \brief Executes the algorithm and check the negative circles. 432 /// 433 /// \pre init() must be called and at least one node should be added 434 /// with addSource() before using this function. If there is 435 /// a negative circle in the graph it gives back false. 436 /// 437 /// This method runs the %BelmannFord algorithm from the root node(s) 438 /// in order to compute the shortest path to each node. The algorithm 439 /// computes 440 /// - The shortest path tree. 441 /// - The distance of each node from the root(s). 442 bool checkedStart() { 443 int num = countNodes(*graph); 444 for (int i = 0; i < num; ++i) { 445 bool ready = true; 446 for (EdgeIt it(*graph); it != INVALID; ++it) { 447 Node source = graph->source(it); 448 Node target = graph->target(it); 449 Value relaxed = 450 OperationTraits::plus((*_dist)[source], (*length)[it]); 451 if (OperationTraits::less(relaxed, (*_dist)[target])) { 452 _pred->set(target, it); 453 _dist->set(target, relaxed); 454 ready = false; 455 } 456 } 457 if (ready) return true; 458 } 459 return false; 420 460 } 421 461
Note: See TracChangeset
for help on using the changeset viewer.