最短路径算法――Dijkstra

#include 
  
   
#include 
   
     #include 
    
      void shortestpath( const std::vector 
     
       >& paths, int from, std::vector< short>& path){ std:: vector
      
        flags(paths.size(), false); std:: vector
       
         distance(paths.size(), 0); path.resize(paths.size(), 0); for(size_t i = 0; i != paths.size(); ++i){ distance[i] = paths[from][i]; } flags[from] = 1; int min, pos; for(size_t i = 1; i != paths.size(); ++i){ pos = -1; min = std:: numeric_limits
        
         ::max(); for(size_t j = 0; j != paths.size(); ++j){ if(!flags[j] && distance[j] < min){ min = distance[j]; pos = j; } } if(pos == -1) break; flags[pos] = true; for(size_t j = 0; j != paths.size(); ++j){ if(!flags[j] && paths[pos][j] != 0 && paths[pos][j] < std::numeric_limits 
         
          :: max() && min+paths[pos][j] < distance[j]){ distance[j] = min + paths[pos][j]; path[j] = pos; } } } for(size_t i = 0; i != distance.size(); ++i){ std::cout << distance[i] << " " << 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
            
              path; shortestpath(paths, 0, path); std::cout << "最近路径结果为：" << std::flush; for(size_t i = 0; i != path.size(); ++i){ std::cout << path[i] << " " << std::flush; } std::cout << std:: endl; return 0; }
            
           
          
         
        
       
      
     
    
   
  

本文链接：http://blog.csdn.net/girlkoo/article/details/17524923

本文作者：girlkoo