c++ - C++ 修改 Djikstra 的算法以给出第二个最短路径
问题描述
你如何修改这个 Djikstra 的算法来给出第二个最短路径?我完成此功能的另一种方法是使用 **G 传递动态初始化的二维数组。
我了解这里的最短路径,但是第二条最短路径令人困惑。
int main() {
int G[max][max]={{0,1,0,3,10},{1,0,5,0,0},{0,5,0,2,1},{3,0,2,0,6},{10,0,1,6,0}};
int n=5;
int u=0;
dijkstra(G,n,u);
return 0;
}
void dijkstra(int G[max][max],int n,int startnode) {
int cost[max][max],distance[max],pred[max];
int visited[max],count,mindistance,nextnode,i,j;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(G[i][j]==0)
cost[i][j]=INFINITY;
else
cost[i][j]=G[i][j];
for(i=0;i<n;i++) {
distance[i]=cost[startnode][i];
pred[i]=startnode;
visited[i]=0;
}
distance[startnode]=0;
visited[startnode]=1;
count=1;
while(count<n-1) {
mindistance=INFINITY;
for(i=0;i<n;i++)
if(distance[i]<mindistance&&!visited[i]) {
mindistance=distance[i];
nextnode=i;
}
visited[nextnode]=1;
for(i=0;i<n;i++)
if(!visited[i])
if(mindistance+cost[nextnode][i]<distance[i]) {
distance[i]=mindistance+cost[nextnode][i];
pred[i]=nextnode;
}
count++;
}
for(i=0;i<n;i++)
if(i!=startnode) {
cout<<"\nDistance of node"<<i<<"="<<distance[i];
cout<<"\nPath="<<i;
j=i;
do {
j=pred[j];
cout<<"<-"<<j;
}while(j!=startnode);
}
}
This algorithm is from tutorials point.
解决方案
推荐阅读
- jquery - jQuery通过多个属性和范围过滤项目
- php - 类 'App\Category' 未找到 CategoriesController.php
- delphi - 在 Delphi 中使用 CreateProcess 时跳过 UAC 提示
- html - 在 PL/SQL 动态内容中将变量传递给 htp.p
- css - 如果 CSS 内容包含未声明的 CSS 变量,是否应该显示它?
- vue.js - v-根据标签选择数据搜索
- c# - EF Core 理解迁移
- c - 为什么需要 -pthread 作为编译 pthread c 程序的参数
- swift - NSMutableAttributedString 的 UserDefaults
- r - 如何在 .Rprofile 中配置主题编辑器和默认编码