equal
deleted
inserted
replaced
417 } |
417 } |
418 |
418 |
419 /// \brief Executes one round from the belmann ford algorithm. |
419 /// \brief Executes one round from the belmann ford algorithm. |
420 /// |
420 /// |
421 /// If the algoritm calculated the distances in the previous round |
421 /// If the algoritm calculated the distances in the previous round |
422 /// strictly for all at most k length pathes then it will calculate the |
422 /// strictly for all at most k length paths then it will calculate the |
423 /// distances strictly for all at most k + 1 length pathes. With k |
423 /// distances strictly for all at most k + 1 length paths. With k |
424 /// iteration this function calculates the at most k length pathes. |
424 /// iteration this function calculates the at most k length paths. |
|
425 ///\todo what is the return value? |
425 bool processNextRound() { |
426 bool processNextRound() { |
426 for (int i = 0; i < (int)_process.size(); ++i) { |
427 for (int i = 0; i < (int)_process.size(); ++i) { |
427 _mask->set(_process[i], false); |
428 _mask->set(_process[i], false); |
428 } |
429 } |
429 std::vector<Node> nextProcess; |
430 std::vector<Node> nextProcess; |
450 } |
451 } |
451 |
452 |
452 /// \brief Executes one weak round from the belmann ford algorithm. |
453 /// \brief Executes one weak round from the belmann ford algorithm. |
453 /// |
454 /// |
454 /// If the algorithm calculated the distances in the |
455 /// If the algorithm calculated the distances in the |
455 /// previous round at least for all at most k length pathes then it will |
456 /// previous round at least for all at most k length paths then it will |
456 /// calculate the distances at least for all at most k + 1 length pathes. |
457 /// calculate the distances at least for all at most k + 1 length paths. |
457 /// This function does not make possible to calculate strictly the |
458 /// This function does not make it possible to calculate strictly the |
458 /// at most k length minimal pathes, this way it called just weak round. |
459 /// at most k length minimal paths, this is why it is |
|
460 /// called just weak round. |
|
461 ///\todo what is the return value? |
459 bool processNextWeakRound() { |
462 bool processNextWeakRound() { |
460 for (int i = 0; i < (int)_process.size(); ++i) { |
463 for (int i = 0; i < (int)_process.size(); ++i) { |
461 _mask->set(_process[i], false); |
464 _mask->set(_process[i], false); |
462 } |
465 } |
463 std::vector<Node> nextProcess; |
466 std::vector<Node> nextProcess; |
521 /// \pre init() must be called and at least one node should be added |
524 /// \pre init() must be called and at least one node should be added |
522 /// with addSource() before using this function. |
525 /// with addSource() before using this function. |
523 /// |
526 /// |
524 /// This method runs the %BelmannFord algorithm from the root node(s) |
527 /// This method runs the %BelmannFord algorithm from the root node(s) |
525 /// in order to compute the shortest path with at most \c length edge |
528 /// in order to compute the shortest path with at most \c length edge |
526 /// long pathes to each node. The algorithm computes |
529 /// long paths to each node. The algorithm computes |
527 /// - The shortest path tree. |
530 /// - The shortest path tree. |
528 /// - The limited distance of each node from the root(s). |
531 /// - The limited distance of each node from the root(s). |
529 void limitedStart(int length) { |
532 void limitedStart(int length) { |
530 for (int i = 0; i < length; ++i) { |
533 for (int i = 0; i < length; ++i) { |
531 if (processNextRound()) break; |
534 if (processNextRound()) break; |