最短路径算法――Floyd

#include 
  
   
#include 
   
     #include 
    
      void shortest_floyd(const std::vector 
     
       >& graphic, std::vector 
      
        >& paths){ paths.clear(); std:: vector
       
         tmp; for(size_t i = 0; i != graphic.size(); ++ i){ tmp.push_back( i); } for(size_t i = 0; i != graphic.size(); ++i){ paths.push_back(tmp); } std:: vector
        
          > distance(graphic); std::cout << "路径信息：" << std::endl; for(size_t i = 0; i != distance.size(); ++i){ for(size_t j = 0; j != distance[i].size(); ++j){ std::cout << distance[i][j] << " " << std::flush; } std::cout << std:: endl; } for(size_t k = 0; k != graphic.size(); ++k){ for(size_t i = 0; i != graphic.size(); ++i){ for(size_t j = 0; j != graphic.size(); ++j){ if(distance[i][k]+distance[k][j] < distance[i][j]){ distance[i][j] = distance[i][k]+distance[k][j]; paths[i][j] = paths[i][k]; } } } } std::cout << "距离数组：" << std::endl; for(size_t i = 0; i != distance.size(); ++i){ for(size_t j = 0; j != distance[i].size(); ++j){ std::cout << distance[i][j] << " " << std::flush; } std::cout << std:: endl; } } int main(){ std::cout << "请输入顶点数：" << std::flush; int sum; std::cin >





> sum; std:: vector
         
           > paths; for(int i = 0; i != sum; ++i){ paths.push_back(std:: vector
          
           (sum, std::numeric_limits< short>::max())); paths[i][i] = 0; } std::cout << "请输入边数：" << std::flush; std::cin >> sum; int vi, vj, weight; for(int i = 0; i != sum; ++i){ std::cin >> vi >> vj >> weight; paths[vi][vj] = weight; paths[vj][vi] = weight; } std:: vector
           
             > result; shortest_floyd(paths, result); std::cout << "最短路径矩阵" << std::endl; for(size_t i = 0; i != result.size(); ++i){ for(size_t j = 0; j != result[i].size(); ++j){ std::cout << result[i][j] << " " << std::flush; } std::cout << std:: endl; } return 0; }