TWiki > Doc > CodeExamples > GraphParametricTypeExample > JohnsonAllPairsShortestPathsExample	TWiki webs: Dev | Doc | Main | TWiki | Sandbox
	Doc . { Changes | Index | Search | Go }

// compilation unit Johnson.nice
package graph;

<Edge,Graph,Distance,Vertex,ReadWritePM | 
Edge <: GraphEdge<Vertex>,
ReadWritePM <: ReadWritePropertyMap<Vertex, Distance>
>
boolean johnsonAllPairsShortestPaths(
   VertexListAndIncidenceAndEdgeListGraph<Vertex,Edge> graph,
   ReadablePropertyMap<Edge, Distance> w,
   ReadWritePropertyMap<Edge, Distance> w2,
   ReadWritePropertyMap<Vertex, Distance> distance,
   ReadablePropertyMap<Vertex, ReadWritePM> distanceMatrix,
   Distance zero,
   Distance inf,
   (Distance, Distance)->Distance combine,
   Distance->Distance negate,
   (Distance, Distance)->boolean compare
   ){

   // Set distance to all vertices to zero (emulates special "s" vertex used in CLR)
   for (Vertex v : graph.vertices())
      distance[v] = zero;

   // Do Bellman-Ford to get factors for reweighting
   let bfWorked = bellmanFordShortestPaths(
      graph, graph.nVertices(), w, new NullPropertyMap(), 
      distance, combine, compare
      );

   if (!bfWorked) return false; // Negative-weight cycle

   // Set up reweighting
   for (e : graph.edges())
      w2[e] = combine( 
         combine(w[e], distance[e.source]), 
         negate(distance[e.target]) );

   // Do Dijkstra from each vertex
   for (Vertex v : graph.vertices()) { 
      let dm = distanceMatrix[v]; 
       
      dijkstraShortestPaths(
         graph, v, new NullPropertyMap(), dm, 
         w2, compare, combine, inf, zero
         );

       // Adjust returned distances to account for reweighting
      for (Vertex v2 : graph.vertices())
         dm[v2] = combine( 
            combine(dm[v2], distance[v2]), 
            negate(distance[v]) );                         
   }     
   return true;
}