Dijkstra

给定有向带权图，且其中每条边的权值都为非负实数，计算从源点到其他各个顶点的最短路径长度

\(S\)为以确定最短路径的集合，则\(V-S\)为最短路径未确定的集合 - 实质：贪心算法 - 策略：选择特殊路径长度最短的路径，将其连接的\(V-S\)中的顶点加入集合\(S\)，同时更新数组\(dist[]\)。当\(S\)中包含所有顶点时，从源点到任意点的最短路径长度全部被找到

算法步骤

数据结构：设置带权邻接矩阵\(G.Edge[i][j] = w\)，如果非邻接，则令\(G.Edge[i][j] = \infty\)，采用一维数组\(dist[i]\)来记录从源点到顶点\(i\)的最短路径长度，采用一维数组\(p[i]\)来记录最短路径上\(i\)顶点的前驱
初始化：设置\(u\)为源点，初始化最短路径\(dist[i] = G.Edge[u][i]\)，初始化前驱\(p[i]\)为\(u\)
找最小：在\(V-S\)中找\(dist[i]\)最小的顶点\(t\)，\(t\)确定为已找到最短路径，更新两个集合
判断：如果\(V-S\)空，则直接结束，否则继续下一步
松弛操作：利用在第三步中找到的最近点\(t\)，去尝试更新\(t\)的邻接点\(j\)，即如果\(dist[j]>dist[t]+G.Edge[t][j]\)，则令\(dist[j]=dist[t]+G.Edge[t][j]\)，并且同时更新\(j\)的前驱为\(t\)，继续进行第三步的操作

复杂度

时间复杂度：\(O(n^2)\)
空间复杂度：邻接矩阵：\(O(n)\)，邻接表：\(O(E)\)

优化

利用优先队列来优化寻找最近顶点的操作，降低时间复杂度
对于稀疏图，采用邻接表的方式存储图，对于稠密图，使用邻接矩阵，降低空间复杂度

朴素Dijkstra

适用于稠密图，使用邻接矩阵来解决

解题思路

初始化距离
1. dst[1] = 0; dst[其他] = 0x3f3f3f3f; 第一个点的距离为一，其他点未确定，记为无穷大
2. st[]用于标记点，记录当前点是否已找到最短距离
for(int i = 1;i <= n;i++)
1. 寻找距离i点(不在s中)最近的节点t
2. 标记节点t，表明t节点的最短距离已经找到
3. 遍历与\(i\)连接的节点，并更新距离（但不一定是最短，不做标记）

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

const int N = 510;
int n, m;

int g[N][N], dst[N];
bool st[N];

int dijkstra(){
    memset(dst, 0x3f, sizeof dst);
    dst[1] = 0;

    for(int i = 1;i <= n;i++){
        int t = -1;             //初始化距离最短的节点（未知）
        for(int j = 1;j <= n;j++){          //寻找最短未寻边
            if(!st[j] && (t == -1 || dst[t] > dst[j])){     
                t = j;
            }
        }

        st[t] = true;       //标记最短的点，表明当前点的最短距离已找到

        for(int j = 1;j <= n;j++){    //利用t更新其他邻接点的最短距离
            dst[j] = min(dst[j], dst[t] + g[t][j]);     //更新距离
        }
    }

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

int main(){
    cin >> n >> m;

    memset(g, 0x3f, sizeof g);

    while(m--){
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        g[a][b] = min(g[a][b], c);
    }

    int t = dijkstra();

    cout << t;

    return 0;
}

时间复杂度高可以使用普通二叉堆（堆中应该存储的数据为结点与距离）或斐波那契堆优化