410 /// - The shortest path tree. |
410 /// - The shortest path tree. |
411 /// - The distance of each node from the root(s). |
411 /// - The distance of each node from the root(s). |
412 void start() { |
412 void start() { |
413 int num = countNodes(*graph) - 1; |
413 int num = countNodes(*graph) - 1; |
414 for (int i = 0; i < num; ++i) { |
414 for (int i = 0; i < num; ++i) { |
415 bool ready = true; |
415 bool done = true; |
416 for (EdgeIt it(*graph); it != INVALID; ++it) { |
416 for (EdgeIt it(*graph); it != INVALID; ++it) { |
417 Node source = graph->source(it); |
417 Node source = graph->source(it); |
418 Node target = graph->target(it); |
418 Node target = graph->target(it); |
419 Value relaxed = |
419 Value relaxed = |
420 OperationTraits::plus((*_dist)[source], (*length)[it]); |
420 OperationTraits::plus((*_dist)[source], (*length)[it]); |
421 if (OperationTraits::less(relaxed, (*_dist)[target])) { |
421 if (OperationTraits::less(relaxed, (*_dist)[target])) { |
422 _pred->set(target, it); |
422 _pred->set(target, it); |
423 _dist->set(target, relaxed); |
423 _dist->set(target, relaxed); |
424 ready = false; |
424 done = false; |
425 } |
425 } |
426 } |
426 } |
427 if (ready) return; |
427 if (done) return; |
428 } |
428 } |
429 } |
429 } |
430 |
430 |
431 /// \brief Executes the algorithm and check the negative circles. |
431 /// \brief Executes the algorithm and checks the negative circles. |
432 /// |
432 /// |
433 /// \pre init() must be called and at least one node should be added |
433 /// \pre init() must be called and at least one node should be added |
434 /// with addSource() before using this function. If there is |
434 /// with addSource() before using this function. If there is |
435 /// a negative circle in the graph it gives back false. |
435 /// a negative circle in the graph it gives back false. |
436 /// |
436 /// |
440 /// - The shortest path tree. |
440 /// - The shortest path tree. |
441 /// - The distance of each node from the root(s). |
441 /// - The distance of each node from the root(s). |
442 bool checkedStart() { |
442 bool checkedStart() { |
443 int num = countNodes(*graph); |
443 int num = countNodes(*graph); |
444 for (int i = 0; i < num; ++i) { |
444 for (int i = 0; i < num; ++i) { |
445 bool ready = true; |
445 bool done = true; |
446 for (EdgeIt it(*graph); it != INVALID; ++it) { |
446 for (EdgeIt it(*graph); it != INVALID; ++it) { |
447 Node source = graph->source(it); |
447 Node source = graph->source(it); |
448 Node target = graph->target(it); |
448 Node target = graph->target(it); |
449 Value relaxed = |
449 Value relaxed = |
450 OperationTraits::plus((*_dist)[source], (*length)[it]); |
450 OperationTraits::plus((*_dist)[source], (*length)[it]); |
451 if (OperationTraits::less(relaxed, (*_dist)[target])) { |
451 if (OperationTraits::less(relaxed, (*_dist)[target])) { |
452 _pred->set(target, it); |
452 _pred->set(target, it); |
453 _dist->set(target, relaxed); |
453 _dist->set(target, relaxed); |
454 ready = false; |
454 done = false; |
455 } |
455 } |
456 } |
456 } |
457 if (ready) return true; |
457 if (done) return true; |
458 } |
458 } |
459 return false; |
459 return false; |
460 } |
460 } |
461 |
461 |
462 /// \brief Runs %BelmannFord algorithm from node \c s. |
462 /// \brief Runs %BelmannFord algorithm from node \c s. |