COIN-OR::LEMON - Graph Library

Changeset 1747:bccf2379b5dd in lemon-0.x for lemon/johnson.h


Ignore:
Timestamp:
10/28/05 11:01:59 (14 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2275
Message:

Faster implementation

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/johnson.h

    r1741 r1747  
    495495    void shiftedRun(const BelmannFordType& belmannford) {
    496496     
    497       typedef PotentialDifferenceMap<Graph,
    498       typename BelmannFordType::DistMap> PotDiffMap;
    499       PotDiffMap potdiff(*graph, belmannford.distMap());
    500       typedef SubMap<LengthMap, PotDiffMap> ShiftLengthMap;
    501       ShiftLengthMap shiftlen(*length, potdiff);
    502 
    503       typename Dijkstra<Graph, ShiftLengthMap>::
    504       template DefHeap<Heap, HeapCrossRef>::Create dijkstra(*graph, shiftlen);
     497      typename Graph::template EdgeMap<Value> shiftlen(*graph);
     498      for (EdgeIt it(*graph);  it != INVALID; ++it) {
     499        shiftlen[it] = (*length)[it]
     500          + belmannford.dist(graph->source(it))
     501          - belmannford.dist(graph->target(it));
     502      }
     503     
     504      typename Dijkstra<Graph, typename Graph::template EdgeMap<Value> >::
     505        template DefHeap<Heap, HeapCrossRef>::
     506        Create dijkstra(*graph, shiftlen);
    505507
    506508      dijkstra.heap(*_heap, *_heap_cross_ref);
Note: See TracChangeset for help on using the changeset viewer.