TWiki > Doc > CodeExamples > GraphParametricTypeExample > BellmanFordShortestPathsExample	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;
}