418 } |
418 } |
419 } |
419 } |
420 |
420 |
421 /// \brief Executes one round from the bellman ford algorithm. |
421 /// \brief Executes one round from the bellman ford algorithm. |
422 /// |
422 /// |
423 /// If the algoritm calculated the distances in the previous round |
423 /// If the algoritm calculated the distances in the previous round |
424 /// strictly for all at most k length paths then it will calculate the |
424 /// exactly for all at most \f$ k \f$ length path lengths then it will |
425 /// distances strictly for all at most k + 1 length paths. With k |
425 /// calculate the distances exactly for all at most \f$ k + 1 \f$ |
426 /// iteration this function calculates the at most k length paths. |
426 /// length path lengths. With \f$ k \f$ iteration this function |
427 /// \return %True when the algorithm have not found more shorter paths. |
427 /// calculates the at most \f$ k \f$ length path lengths. |
|
428 /// |
|
429 /// \warning The paths with limited edge number cannot be retrieved |
|
430 /// easily with \ref getPath() or \ref predEdge() functions. If you |
|
431 /// need the shortest path and not just the distance you should store |
|
432 /// after each iteration the \ref predEdgeMap() map and manually build |
|
433 /// the path. |
|
434 /// |
|
435 /// \return %True when the algorithm have not found more shorter |
|
436 /// paths. |
428 bool processNextRound() { |
437 bool processNextRound() { |
429 for (int i = 0; i < (int)_process.size(); ++i) { |
438 for (int i = 0; i < (int)_process.size(); ++i) { |
430 _mask->set(_process[i], false); |
439 _mask->set(_process[i], false); |
431 } |
440 } |
432 std::vector<Node> nextProcess; |
441 std::vector<Node> nextProcess; |
524 /// \brief Executes the algorithm with path length limit. |
533 /// \brief Executes the algorithm with path length limit. |
525 /// |
534 /// |
526 /// \pre init() must be called and at least one node should be added |
535 /// \pre init() must be called and at least one node should be added |
527 /// with addSource() before using this function. |
536 /// with addSource() before using this function. |
528 /// |
537 /// |
529 /// This method runs the %BellmanFord algorithm from the root node(s) |
538 /// This method runs the %BellmanFord algorithm from the root |
530 /// in order to compute the shortest path with at most \c length edge |
539 /// node(s) in order to compute the shortest path lengths with at |
531 /// long paths to each node. The algorithm computes |
540 /// most \c num edge. |
532 /// - The shortest path tree. |
541 /// |
|
542 /// \warning The paths with limited edge number cannot be retrieved |
|
543 /// easily with \ref getPath() or \ref predEdge() functions. If you |
|
544 /// need the shortest path and not just the distance you should store |
|
545 /// after each iteration the \ref predEdgeMap() map and manually build |
|
546 /// the path. |
|
547 /// |
|
548 /// The algorithm computes |
|
549 /// - The predecessor edge from each node. |
533 /// - The limited distance of each node from the root(s). |
550 /// - The limited distance of each node from the root(s). |
534 void limitedStart(int length) { |
551 void limitedStart(int num) { |
535 for (int i = 0; i < length; ++i) { |
552 for (int i = 0; i < num; ++i) { |
536 if (processNextRound()) break; |
553 if (processNextRound()) break; |
537 } |
554 } |
538 } |
555 } |
539 |
556 |
540 /// \brief Runs %BellmanFord algorithm from node \c s. |
557 /// \brief Runs %BellmanFord algorithm from node \c s. |