算法 朴素Dijkstra

所需存储的数组

1.根据题目这里m和n*n是一个数量级的所以是一个稠密图，用邻接矩阵来存g[i][j];

2.dist数组表示每个点到起点的最短距离

3.st[i]集合表示第i个点是否已经确定最短距离，如果是1表示在却定了最短距离，反则不是

实现方法

1.把所有点到起点的距离都初始化为正无穷，起点到自己的最短距离为；

2.进行n次操作确定n个点的最短距离（把所有点都加入到st集合中）；

3.每次从集合中选出不在集合中且到起点最短的那个点；

4.把此点加入到集合st中；

5.再以此点为中心向其连接的点进行扩展

6.最后返回终点到起点的最短距离就行了

关于第3步初步的理解

因为是不在集合st中dist且最小的点，他一定就是这个点到起点的最短距离

因为都是正权边，所以跟他同一层级（也就是同一次i迭代的时候）的其他点都比他大，再经过其转移过来还的加上他到不在集合且dist最小点的权值，变得更大了；

所以起点到不在集合且dist最小的点一定就是最短距离

时间复杂度O（N*N）

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int g[N][N],st[N],dist[N];
int n,m;
int dijkstra()
{
    memset(dist,0x3f,sizeof dist);//1
    dist[1]=0;
    for(int i=1;i<=n;i++)//2
    {
        int t=-1;//3
        for(int j=1;j<=n;j++)
        {
            if(!st[j]&&(t==-1||dist[t]>dist[j]))t=j;
        }
        st[t]=1;//4
        for(int j=1;j<=n;j++)//5
            dist[j]=min(dist[j],dist[t]+g[t][j]);
    }
    if(dist[n]==0x3f3f3f3f)return -1;//6
    else return dist[n]; 
}
int main()
{
    cin>>n>>m;
    memset(g,0x3f,sizeof g);
    while(m--)
    {
        int a,b,w;
        cin>>a>>b>>w;
        g[a][b]=min(g[a][b],w);
    }
    cout<<dijkstra();
}

大佬误喷

下一篇Dijkstra堆优化版 https://www.acwing.com/solution/content/17504/