Dijkstra算法求单源最短路径

Dijkstra算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。
把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径 , 就将加入到集合S中，直到全部顶点都加入到S中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。

时间复杂度 $O(n^2+m)$

C++ 代码

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

const int N = 501;
int g[N][N];  //邻接矩阵
int dist[N];  //dist[i]表示1到i的最短路径
int st[N];  //st[i]表示是否找到1到i的最短路径
int n,m;

int dijkstra(){
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 0;
    for(int i=0; i<n; i++){
        int t = -1;  //t是未找到最短路径的点，初始化为-1
        for(int j=1; j<=n; j++)
            if(!st[j] && (t==-1 || dist[t]>dist[j])) t=j; //在未找到最短路径的点中找到最小值
        for(int j=1; j<=n; j++){
            dist[j] = min(dist[j], dist[t]+g[t][j]);  //更新
        }
        st[t] = 1; 
    }

    if(dist[n]==0x3f3f3f3f)return -1;
    else return dist[n];
}

int main(){
    ios::sync_with_stdio(0);
    memset(g,0x3f,sizeof(g));
    cin>>n>>m;
    for(int i=1; i<=m; i++){
        int a,b,c;
        cin>>a>>b>>c;
        g[a][b] = min(g[a][b],c);
    }
    cout<<dijkstra();
    return 0;
}