Changeset 1754:4bf5ceb49023 in lemon-0.x for lemon/johnson.h
- Timestamp:
- 11/02/05 16:27:38 (19 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2283
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/johnson.h
r1747 r1754 176 176 }; 177 177 178 /// \brief Johnson algorithm class.178 /// \brief %Johnson algorithm class. 179 179 /// 180 180 /// \ingroup flowalgs 181 /// This class provides an efficient implementation of \c Johnson181 /// This class provides an efficient implementation of \c %Johnson 182 182 /// algorithm. The edge lengths are passed to the algorithm using a 183 183 /// \ref concept::ReadMap "ReadMap", so it is easy to change it to any … … 186 186 /// The algorithm solves the shortest path problem for each pairs 187 187 /// of node when the edges can have negative length but the graph should 188 /// not contain c irclewith negative sum of length. If we can assume188 /// not contain cycles with negative sum of length. If we can assume 189 189 /// that all edge is non-negative in the graph then the dijkstra algorithm 190 190 /// should be used from each node. … … 378 378 } 379 379 }; 380 ///\ ref named-templ-param "Named parameter" for setting heap and cross381 /// reference type380 ///\brief \ref named-templ-param "Named parameter" for setting heap and 381 ///cross reference type 382 382 383 383 ///\ref named-templ-param "Named parameter" for setting heap and cross … … 488 488 protected: 489 489 490 typedef typename BelmannFord<Graph, LengthMap>:: 491 template DefOperationTraits<OperationTraits>:: 492 template DefPredMap<NullMap<Node, Edge> >:: 493 Create BelmannFordType; 494 495 void shiftedRun(const BelmannFordType& belmannford) { 490 template <typename PotentialMap> 491 void shiftedRun(const PotentialMap& potential) { 496 492 497 493 typename Graph::template EdgeMap<Value> shiftlen(*graph); 498 494 for (EdgeIt it(*graph); it != INVALID; ++it) { 499 495 shiftlen[it] = (*length)[it] 500 + belmannford.dist(graph->source(it))501 - belmannford.dist(graph->target(it));496 + potential[graph->source(it)] 497 - potential[graph->target(it)]; 502 498 } 503 499 … … 513 509 if (dijkstra.reached(jt)) { 514 510 _dist->set(it, jt, dijkstra.dist(jt) + 515 belmannford.dist(jt) - belmannford.dist(it));511 potential[jt] - potential[it]); 516 512 _pred->set(it, jt, dijkstra.pred(jt)); 517 513 } else { … … 551 547 void start() { 552 548 549 typedef typename BelmannFord<Graph, LengthMap>:: 550 template DefOperationTraits<OperationTraits>:: 551 template DefPredMap<NullMap<Node, Edge> >:: 552 Create BelmannFordType; 553 553 554 BelmannFordType belmannford(*graph, *length); 554 555 … … 560 561 belmannford.start(); 561 562 562 shiftedRun(belmannford );563 } 564 565 /// \brief Executes the algorithm and checks the negatvie c ircles.563 shiftedRun(belmannford.distMap()); 564 } 565 566 /// \brief Executes the algorithm and checks the negatvie cycles. 566 567 /// 567 568 /// This method runs the %Johnson algorithm in order to compute 568 569 /// the shortest path to each node pairs. If the graph contains 569 /// negative c ircle it gives back false. The algorithm570 /// negative cycle it gives back false. The algorithm 570 571 /// computes 571 572 /// - The shortest path tree for each node. 572 573 /// - The distance between each node pairs. 573 574 bool checkedStart() { 575 576 typedef typename BelmannFord<Graph, LengthMap>:: 577 template DefOperationTraits<OperationTraits>:: 578 template DefPredMap<NullMap<Node, Edge> >:: 579 Create BelmannFordType; 574 580 575 581 BelmannFordType belmannford(*graph, *length); … … 582 588 if (!belmannford.checkedStart()) return false; 583 589 584 shiftedRun(belmannford );590 shiftedRun(belmannford.distMap()); 585 591 return true; 586 592 }
Note: See TracChangeset
for help on using the changeset viewer.