网站挑错/韶山百度seo

Floyd算法相比Dijkstra算法最大的区别是计算出了任意点起始到任意点的最短路径，算法也不难理解，需要注意的是三层for循环的顺序问题，k必须为最外层循环，具体的代码如下：

#include <iostream>
#include <vector>
#include <limits>void shortest_floyd(const std::vector <std::vector< short> >& graphic, std::vector <std::vector< short> >& paths){paths.clear();std:: vector<short> 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<std::vector <short> > 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<std::vector <short> > paths;for(int i = 0; i != sum; ++i){paths.push_back(std:: vector<short>(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<std::vector <short> > 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;
}

本文链接： http://blog.csdn.net/girlkoo/article/details/17525029
本文作者：girlkoo