最短路径C++算法模板
看了算法笔记,记录Dijkstra算法模板,Dijkstra算法是单源最短路径算法
#define maxv 1001
#define INF 0x3fffffff
int G[maxv][maxv];//邻接矩阵存储图
int d[maxv], n; // n 是顶点数
bool vis[maxv] = {false};
void dijkstra(int s){//对点s进行最短路径算法
fill(d, d + maxv, INF);//初始化所有顶点到源s的距离为无穷大
d[s] = 0;//s到自己的距离为0
for(int i = 0;i < n;i++){//对每个顶点进行遍历
int u = -1, Min = INF;
for(int j = 0;j < n;j++){//找到距离s最近的未访问过的顶点u
if(!vis[j] && d[j] < Min){
Min = d[j];
u = j;
}
}
if(u == -1) return;//图是不连通的
vis[u] = true;//访问顶点u
for(int v = 0;v < n;v++) {
if(!vis[v] && G[u][v] != INF && d[u] + G[u][v] < d[v]){//如果s通过中间顶点u到v的距离比原来s到v的距离更短则更新该距离
d[v] = d[u] + G[u][v];
}
}
}
}
原文链接: https://www.cnblogs.com/Codroc/p/12458770.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/334491
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!