时间:2021-05-20
Dijkstra的最短路径算法是基于前驱顶点的最短路径计算的,整体上来讲还是比较简单的,下面是代码:
复制代码 代码如下:
#include <iostream>
#include <vector>
#include <limits>
void shortestpath( const std::vector <std::vector< short> >& paths, int from, std::vector< short>& path){
std:: vector<bool> flags(paths.size(), false);
std:: vector<short> 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<short>::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 <int>:: 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<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<short> 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;
}
声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。
最短路径问题(python实现)解决最短路径问题:(如下三种算法)(1)迪杰斯特拉算法(Dijkstra算法)(2)弗洛伊德算法(Floyd算法)(3)SPFA
一、Dijkstra算法的思路Dijkstra算法是针对单源点求最短路径的算法。其主要思路如下:1.将顶点分为两部分:已经知道当前最短路径的顶点集合Q和无法到达
Dijkstra算法Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法,是广度优先算法的一种,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始
本文实例讲述了Python数据结构与算法之图的最短路径(Dijkstra算法)。分享给大家供大家参考,具体如下:#coding:utf-8#Dijkstra算法
本文实例为大家分享了C++计算任意权值单源最短路径的具体代码,供大家参考,具体内容如下一、有Dijkstra算法求最短路径了,为什么还要用Bellman-For