朴素版本的dijkstra算法（有注释）

解题思路:

注意事项:

参考代码:

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int N=55;

int g[N][N];    //为稠密阵所以用邻接矩阵存储
int dist[N];    //用于记录每一个点距离节点编号为u的节点的距离  
bool st[N];     //用于记录该点的最短距离是否已经确定

int n;

void Dijkstra(int u)
{
    memset(dist, 0x3f,sizeof dist);     //初始化距离  0x3f代表无限大  Dijkstra函数结束后d[i]还是无穷大说明下下标为u的点无法到达i号节点
    
    dist[u]=0;  //u号点到自身的距离为0
    
    for(int i=0;i<n;i++)      //有n个点所以要进行n次 迭代
    {
        int t=-1;       //t存储当前访问的点
        
        for(int j=0;j<n;j++)   //这里的j代表的是从编号为0号点开始
            if(!st[j]&&(t==-1||dist[t]>dist[j]))     
                t=j;
        
        st[t]=true;   
        
        for(int j=0;j<n;j++)           //依次更新每个点所到相邻的点路径值
            dist[j]=min(dist[j],dist[t]+g[t][j]);
    }
}
int main()
{
    scanf("%d",&n);
    
    memset(g,0x3f,sizeof g);    //初始化图 因为是求最短路径
    //所以每个点初始为无限大
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            scanf("%d",&g[i][j]);
    

    Dijkstra(0); //求0号点到其他点的距离，调用就可
    if(dist[n-1]==0x3f3f3f3f) printf("-1\n");  //如果第n个点路径为无穷大即不存在最低路径
    else printf("%d\n",dist[n-1]);
}