这篇文章主要介绍了Dijkstra最短路径算法实现代码,有需要的朋友可以参考一下
Dijkstra的最短路径算法是基于前驱顶点的最短路径计算的,整体上来讲还是比较简单的,下面是代码:
#include
#include
#include
void shortestpath( const std::vector
std:: vector
std:: vector
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
for(size_t j = 0; j != paths.size(); ++j){
if(!flags[j] && 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]
&& 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
for(int i = 0; i != sum; ++i){
paths.push_back(std:: vector
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
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;
}
以上就是Dijkstra最短路径算法实现代码的详细内容,更多请关注0133技术站其它相关文章!