COIN-OR::LEMON - Graph Library

Changeset 1741:7a98fe2ed989 in lemon-0.x for lemon/floyd_warshall.h


Ignore:
Timestamp:
10/26/05 12:50:47 (14 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2269
Message:

Some modifications on shortest path algoritms:

  • heap traits
  • checked execution
File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/floyd_warshall.h

    r1723 r1741  
    393393        for (NodeIt jt(*graph); jt != INVALID; ++jt) {
    394394          _pred->set(it, jt, INVALID);
    395           _dist->set(it, jt, it == jt ?
    396                      OperationTraits::zero() : OperationTraits::infinity());
     395          _dist->set(it, jt, OperationTraits::infinity());
    397396        }
     397        _dist->set(it, it, OperationTraits::zero());
    398398      }
    399399      for (EdgeIt it(*graph); it != INVALID; ++it) {
     
    427427        }
    428428      }
     429    }
     430
     431    /// \brief Executes the algorithm and checks the negative circles.
     432    ///
     433    /// This method runs the %FloydWarshall algorithm in order to compute
     434    /// the shortest path to each node pairs. If there is a negative circle
     435    /// in the graph it gives back false.
     436    /// The algorithm computes
     437    /// - The shortest path tree for each node.
     438    /// - The distance between each node pairs.
     439    bool checkedStart() {
     440      start();
     441      for (NodeIt it(*graph); it != INVALID; ++it) {
     442        if (OperationTraits::less((*dist)(it, it), OperationTraits::zero())) {
     443          return false;
     444        }
     445      }
     446      return true;
    429447    }
    430448   
Note: See TracChangeset for help on using the changeset viewer.