equal
deleted
inserted
replaced
433 /// easily with \ref path() or \ref predEdge() functions. If you |
433 /// easily with \ref path() or \ref predEdge() functions. If you |
434 /// need the shortest path and not just the distance you should store |
434 /// need the shortest path and not just the distance you should store |
435 /// after each iteration the \ref predMap() map and manually build |
435 /// after each iteration the \ref predMap() map and manually build |
436 /// the path. |
436 /// the path. |
437 /// |
437 /// |
438 /// \return %True when the algorithm have not found more shorter |
438 /// \return \c true when the algorithm have not found more shorter |
439 /// paths. |
439 /// paths. |
440 bool processNextRound() { |
440 bool processNextRound() { |
441 for (int i = 0; i < int(_process.size()); ++i) { |
441 for (int i = 0; i < int(_process.size()); ++i) { |
442 _mask->set(_process[i], false); |
442 _mask->set(_process[i], false); |
443 } |
443 } |
470 /// previous round at least for all at most k length paths then it will |
470 /// previous round at least for all at most k length paths then it will |
471 /// calculate the distances at least for all at most k + 1 length paths. |
471 /// calculate the distances at least for all at most k + 1 length paths. |
472 /// This function does not make it possible to calculate strictly the |
472 /// This function does not make it possible to calculate strictly the |
473 /// at most k length minimal paths, this is why it is |
473 /// at most k length minimal paths, this is why it is |
474 /// called just weak round. |
474 /// called just weak round. |
475 /// \return %True when the algorithm have not found more shorter paths. |
475 /// \return \c true when the algorithm have not found more shorter paths. |
476 bool processNextWeakRound() { |
476 bool processNextWeakRound() { |
477 for (int i = 0; i < int(_process.size()); ++i) { |
477 for (int i = 0; i < int(_process.size()); ++i) { |
478 _mask->set(_process[i], false); |
478 _mask->set(_process[i], false); |
479 } |
479 } |
480 std::vector<Node> nextProcess; |
480 std::vector<Node> nextProcess; |
515 } |
515 } |
516 |
516 |
517 /// \brief Executes the algorithm and checks the negative cycles. |
517 /// \brief Executes the algorithm and checks the negative cycles. |
518 /// |
518 /// |
519 /// \pre init() must be called and at least one node should be added |
519 /// \pre init() must be called and at least one node should be added |
520 /// with addSource() before using this function. If there is |
520 /// with addSource() before using this function. |
521 /// a negative cycle in the graph it gives back false. |
|
522 /// |
521 /// |
523 /// This method runs the %BellmanFord algorithm from the root node(s) |
522 /// This method runs the %BellmanFord algorithm from the root node(s) |
524 /// in order to compute the shortest path to each node. The algorithm |
523 /// in order to compute the shortest path to each node. The algorithm |
525 /// computes |
524 /// computes |
526 /// - The shortest path tree. |
525 /// - The shortest path tree. |
527 /// - The distance of each node from the root(s). |
526 /// - The distance of each node from the root(s). |
|
527 /// |
|
528 /// \return \c false if there is a negative cycle in the graph. |
528 bool checkedStart() { |
529 bool checkedStart() { |
529 int num = countNodes(*graph); |
530 int num = countNodes(*graph); |
530 for (int i = 0; i < num; ++i) { |
531 for (int i = 0; i < num; ++i) { |
531 if (processNextWeakRound()) return true; |
532 if (processNextWeakRound()) return true; |
532 } |
533 } |