481 } |
481 } |
482 _dist = &m; |
482 _dist = &m; |
483 return *this; |
483 return *this; |
484 } |
484 } |
485 |
485 |
486 protected: |
486 public: |
487 |
487 |
|
488 ///\name Execution control |
|
489 /// The simplest way to execute the algorithm is to use |
|
490 /// one of the member functions called \c run(...). |
|
491 /// \n |
|
492 /// If you need more control on the execution, |
|
493 /// Finally \ref start() will perform the actual path |
|
494 /// computation. |
|
495 |
|
496 ///@{ |
|
497 |
|
498 /// \brief Initializes the internal data structures. |
|
499 /// |
|
500 /// Initializes the internal data structures. |
|
501 void init() { |
|
502 create_maps(); |
|
503 } |
|
504 |
|
505 /// \brief Executes the algorithm with own potential map. |
|
506 /// |
|
507 /// This method runs the %Johnson algorithm in order to compute |
|
508 /// the shortest path to each node pairs. The potential map |
|
509 /// can be given for this algorithm which usually calculated |
|
510 /// by the Bellman-Ford algorithm. If the graph does not have |
|
511 /// negative length edge then this start function can be used |
|
512 /// with constMap<Node, int>(0) parameter to omit the running time of |
|
513 /// the Bellman-Ford. |
|
514 /// The algorithm computes |
|
515 /// - The shortest path tree for each node. |
|
516 /// - The distance between each node pairs. |
488 template <typename PotentialMap> |
517 template <typename PotentialMap> |
489 void shiftedRun(const PotentialMap& potential) { |
518 void shiftedStart(const PotentialMap& potential) { |
490 |
|
491 typename Graph::template EdgeMap<Value> shiftlen(*graph); |
519 typename Graph::template EdgeMap<Value> shiftlen(*graph); |
492 for (EdgeIt it(*graph); it != INVALID; ++it) { |
520 for (EdgeIt it(*graph); it != INVALID; ++it) { |
493 shiftlen[it] = (*length)[it] |
521 shiftlen[it] = (*length)[it] |
494 + potential[graph->source(it)] |
522 + potential[graph->source(it)] |
495 - potential[graph->target(it)]; |
523 - potential[graph->target(it)]; |
514 } |
542 } |
515 } |
543 } |
516 } |
544 } |
517 } |
545 } |
518 |
546 |
519 public: |
|
520 |
|
521 ///\name Execution control |
|
522 /// The simplest way to execute the algorithm is to use |
|
523 /// one of the member functions called \c run(...). |
|
524 /// \n |
|
525 /// If you need more control on the execution, |
|
526 /// Finally \ref start() will perform the actual path |
|
527 /// computation. |
|
528 |
|
529 ///@{ |
|
530 |
|
531 /// \brief Initializes the internal data structures. |
|
532 /// |
|
533 /// Initializes the internal data structures. |
|
534 void init() { |
|
535 create_maps(); |
|
536 } |
|
537 |
|
538 /// \brief Executes the algorithm. |
547 /// \brief Executes the algorithm. |
539 /// |
548 /// |
540 /// This method runs the %Johnson algorithm in order to compute |
549 /// This method runs the %Johnson algorithm in order to compute |
541 /// the shortest path to each node pairs. The algorithm |
550 /// the shortest path to each node pairs. The algorithm |
542 /// computes |
551 /// computes |
556 bellmanford.predMap(predMap); |
565 bellmanford.predMap(predMap); |
557 |
566 |
558 bellmanford.init(OperationTraits::zero()); |
567 bellmanford.init(OperationTraits::zero()); |
559 bellmanford.start(); |
568 bellmanford.start(); |
560 |
569 |
561 shiftedRun(bellmanford.distMap()); |
570 shiftedStart(bellmanford.distMap()); |
562 } |
571 } |
563 |
572 |
564 /// \brief Executes the algorithm and checks the negatvie cycles. |
573 /// \brief Executes the algorithm and checks the negatvie cycles. |
565 /// |
574 /// |
566 /// This method runs the %Johnson algorithm in order to compute |
575 /// This method runs the %Johnson algorithm in order to compute |
583 bellmanford.predMap(predMap); |
592 bellmanford.predMap(predMap); |
584 |
593 |
585 bellmanford.init(OperationTraits::zero()); |
594 bellmanford.init(OperationTraits::zero()); |
586 if (!bellmanford.checkedStart()) return false; |
595 if (!bellmanford.checkedStart()) return false; |
587 |
596 |
588 shiftedRun(bellmanford.distMap()); |
597 shiftedStart(bellmanford.distMap()); |
589 return true; |
598 return true; |
590 } |
599 } |
591 |
600 |
592 |
601 |
593 /// \brief Runs %Johnson algorithm. |
602 /// \brief Runs %Johnson algorithm. |