Nice TWiki > Doc > GenericProgrammingIntermediateExample? > BellmanFordShortestPathsExample (r1.1) TWiki webs:
Dev | Doc | Main | TWiki | Sandbox
Doc . { Changes | Index | Search | Go }
// compilation unit BellmanFord.nice
package graph;

<Vertex, Edge, Distance, T | Edge <: GraphEdge<Vertex> > 
boolean bellmanFordShortestPaths(
   EdgeListGraph<Vertex,Edge> graph,
   int size,
   ReadablePropertyMap<Edge,Distance> weightMap,
   ReadWritePropertyMap<Vertex,Vertex> predecessor,
   ReadWritePropertyMap<Vertex,Distance> distance,
   (Distance, Distance)->Distance combine,
   (Distance, Distance)->boolean compare
   ){
   
   for (int i = 0; i < size; ++i) {
      boolean anyRelaxed = false; // Optimization from BGL
      for ( Edge edge : graph.edges )
         if( relax(edge, weightMap, distance, predecessor, combine, compare) )
            anyRelaxed = true; 
                       
      if (!anyRelaxed) break;
   }

   for ( Edge edge : graph.edges() )
      if (compare( 
         combine(weightMap[edge], distance[edge.source]), 
         distance[edge.target])
         )
            return false;

   return true;
}
-- IsaacGouy - 07 Jan 2004

Topic BellmanFordShortestPathsExample . { Edit | Attach | Ref-By | Printable | Diffs | r1.6 | > | r1.5 | > | r1.4 | More }
Revision r1.1 - 07 Jan 2004 - 22:21 GMT - IsaacGouy
Parents: GenericProgrammingIntermediateExample?
Copyright © 1999-2003 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback.