floyd_warshall.cpp

/** Floyd Warshall algorithm
  @Arg: graph data structure defined in graph.h
  @Return: shortest distance table, dist[i][j] = min. cost from i to j
 **/
std::vector<std::vector<int> > floyd_warshall(const Graph& g){
  std::vector<std::vector<int> > dist(g.num_v,std::vector<int>(g.num_v,INT_MAX));

  // Init
  for(std::size_t i=0;i<g.num_v;++i)
    dist[i][i] = 0;
  for(auto it:g.edges){
    // there can be negative self cycle
    if(dist[it.edge.first][it.edge.second] > it.weight)
      dist[it.edge.first][it.edge.second] = it.weight;
  }

  //Recursive, do twice to detect all negative cycles
  for(std::size_t t=0;t<2;++t){

    // d_{ij}^k: the cost of shortest path from i to j using only 0~k-th nodes
    for(std::size_t k=0;k<g.num_v;++k){
      for(std::size_t i=0;i<g.num_v;++i){
        for(std::size_t j=0;j<g.num_v;++j){
          if(dist[i][k] != INT_MAX && dist[k][j] != INT_MAX){
            // No negative cycles
            if(dist[i][k] != INT_MIN && dist[k][j] != INT_MIN){
              //shortest path go through k
              if(dist[i][k] + dist[k][j] < dist[i][j])
                dist[i][j] = dist[i][k] + dist[k][j];
            }
            else
              dist[i][j] = INT_MIN;
            
            //Negative self cycle
            if(i==j && dist[i][j] < 0)
              dist[i][j] = INT_MIN;
          }
        }
      }
    }
  }
  return dist; 
}