Dijkstra算法求最短路径，每一行的解释及思路。

Question

#include<bits/stdc++.h>
#define MAXN 100
#define INIT(arr,n) memset(arr,n,sizeof(arr));
using namespace std;
int n,m;
int path[MAXN];
int dist[MAXN];
int visit[MAXN];
int graph[MAXN][MAXN];
int x,y,z;
int start,finish;
void Dijkstra(int s)
{
    INIT(path,-1);INIT(dist,0x3f);INIT(visit,0);
    dist[s]=0;
    while(true)
    {
        int j=0;
        for(int i=1;i<=n;i++)
            if(!visit[i]&&dist[i]<dist[j])
                j=i;
        if(!j) return;
        visit[j]=1;
        for(int i=1;i<=n;i++)
            if(dist[i]>dist[j]+graph[j][i])
                dist[i]=dist[j]+graph[j][i],path[i]=j;
    }
}
void PrintPath(int finish)
{
    if(finish==-1) return;
    PrintPath(path[finish]);
    cout<<finish<<"->";
}
int main()
{
    cin>>n>>m;
    INIT(graph,0x7f);
    for(int i=0;i<m;i++)
        cin>>x>>y>>z,graph[x][y]=z,graph[y][x]=z;
    cin>>start>>finish;
    Dijkstra(start);
    cout<<dist[finish]<<endl;
    cout<<1;
    PrintPath(finish);
    
    return 0;
}

Answer 1

不知道你这个问题是否已经解决, 如果还没有解决的话:

• 你可以参考下这篇文章：无向图dijkstra算法求最短路径

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 以帮助更多的人 ^-^