COIN-OR::LEMON - Graph Library

Changeset 167:7949a29a334e in lemon-0.x


Ignore:
Timestamp:
03/11/04 13:55:50 (20 years ago)
Author:
jacint
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@238
Message:

* empty log message *

Location:
src/work/jacint
Files:
1 added
2 edited

Legend:

Unmodified
Added
Removed
  • src/work/jacint/dijkstra.cc

    r160 r167  
    2222  double pre_time=currTime();
    2323    Dijkstra<ListGraph, int> dijkstra_test(G, s, cap);
     24    dijkstra_test.run();
    2425  double post_time=currTime();
    2526   
    2627  std::cout << "running time: " << post_time-pre_time << " sec"<< std::endl;
    2728 
     29  int hiba=0;
    2830  EachEdgeIt e;
    29 
    3031  for ( G.getFirst(e) ; G.valid(e); G.next(e) ) {
    3132    NodeIt u=G.tail(e);
    3233    NodeIt v=G.head(e);
    33     assert ( dijkstra_test.dist(v) - dijkstra_test.dist(u) <= cap.get(e) );
     34    if ( dijkstra_test.dist(v) - dijkstra_test.dist(u) > cap.get(e) ) {
     35      std::cout<<"Hiba: "<<dijkstra_test.dist(v) - dijkstra_test.dist(u) - cap.get(e)<<std::endl;
     36      ++hiba;
     37    }
    3438  }
     39
     40  std::cout << "Hibas elek szama: " << hiba << " a " << G.edgeNum() <<"-bol."<< std::endl;
    3541
    3642  return 0;
  • src/work/jacint/dijkstra.h

    r160 r167  
    33 *template <Graph, T, Heap=FibHeap>
    44 *
    5  *
    65 *Constructor:
    76 *
    87 *Dijkstra(Graph G, NodeIt s, Graph::EdgeMap<T> length)
    9  *
    108 *
    119 *
     
    1614 *  The following function should be used after run() was already run.
    1715 *
    18  *
    1916 *T dist(NodeIt v) : returns the distance from s to v.
    2017 *   It is 0 if v is not reachable from s.
    21  *
    2218 *
    2319 *EdgeIt pred(NodeIt v) : returns the last edge
    2420 *   of a shortest s-v path. Returns an invalid iterator
    2521 *   if v=s or v is not reachable from s.
    26  *
    2722 *
    2823 *bool reach(NodeIt v) : true iff v is reachable from s
     
    7772          NodeIt v=heap.top();
    7873          T oldvalue=heap.get(v);
     74          heap.pop();
    7975          distance.set(v, oldvalue);
    80           heap.pop();
    81          
     76
    8277          OutEdgeIt e;
    8378          for( G.getFirst(e,v); G.valid(e); G.next(e)) {
     
    8984                heap.push(w,oldvalue+length.get(e));
    9085                predecessor.set(w,e);
    91 
    9286              } else if ( oldvalue+length.get(e) < heap.get(w) ) {
    9387                predecessor.set(w,e);
     
    115109        return reached.get(v);
    116110      }
    117 
     111     
    118112    };
    119 
     113 
    120114}
    121115
Note: See TracChangeset for help on using the changeset viewer.