Dijkstra

非常经典的单源最短路算法。仅能用于正权图（边权可为 \(0\)）
拥有朴素版 \(O(n^2)\)
和堆优化版 \(O((n + m)\log{m})\)
朴素版一般用邻接矩阵存图
而优化版使用邻接表或者链式前向星，我常用链式前向星

中心思想

每次在没用过的点内找一个距离起点最近的点，用这个点对其他点进行松弛操作。
如果把这个点到起点的最短距离称为边的话，即找最短未使用的边，并用这个边对其他所以边进行松弛。

松弛即利用某个点使得某条边的距离变短，如下图：

可以看出，从 \(1\) 到 \(2\) 的距离为 \(5\)，但从 \(1\) 到 \(3\)，再从\(3\) 到 \(2\) 的总距离仅为 \(3\)，因此就可以用 \(3\) 这个点，对 \(1\) 到 \(2\) 之间的最短距离缩小，即松弛。有点时候我喜欢叫扩展

注意当一个点为用过，说明这个点当时已经有最小距离了。

实操步骤

1. 枚举每个点的 dist，找到最小的未使用的dist
2. 对这个点进行标记
3. 利用这个点对其他点进行松弛也就是，dist[j] = max(dist[j], dist[t] + w[j, t])

正确性证明

可以看成，这是贪心的思想，正常的思路，每次都找最小边，那么最后得到的最短距离也应为最小。
反证法
因为是边权非负，所以每次选取的最短边距离dist是单调不减序列。
设一个点为u，当它被使用后，它的dist为最短距离，如果再此之后，还有其他点k能把他扩展更小，因为每次选的dist单调不减，那么dist[k] >= dist[u]，而两点间距离w[k, u]最小为0，那么dist[k] + w[k, u] >= dist[u]，那么这个点k就无法使得dist[u]更小，那么说明这种情况不可能，从而说明算法是正确的。

从这里也可以看出来，如果上面w[k, u] < 0那么k就有可能吧dist[u]变得更小，而我们是不会再去使用dist[u]去扩展其他点的，也就是说，u之后的一些点无法利用这个dist，变得更小，从而使得我们的算法错误。
例子

可以看出，我们会先用2去把4更新成dist为4。然后才会去用3去更新，这时候，dist[2]会变成-95，但因为2已经使用过了，所以不会再去使用它了，于是dist[4]无法更新，算法错误。

代码

中心思想就是这样，代码也显而易见

朴素dijkstra (邻接表)

dijkstra 正确性来自于贪心 也就是 \(st\) 数组内的数(dist) 必须逐渐变大这样才能保证后面的数更新的时候，当前的第三边dist[t]都是最小值
dist[x]表示x到start的最短距离

int dijkstra()
{
    dist[start] = 0;
    int k = n;
    while (k -- ) // 运行n - 1 次就行 n次一样不错就是多算一遍 可改成 --k
    {
        int t = -1;
        for (int i = 1; i <= n; i ++ )
            if (!st[i] && (t == -1 || dist[t] > dist[i]))
                t = i;
                
        st[t] = true;
        
        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            dist[j] = min(dist[j], dist[t] + w[i]);
        }
    }
    
    return dist[ened];
}

朴素dijkstra 邻接矩阵

看代码或者理论应该就能看出来，是 \(O(n^2)\) 的

int dijkstra()
{
    dist[start] = 0;
    int k = n;
    
    while (k -- )
    {
        int t = -1;
        for (int i = 1; i <= n; i ++ )
            if (!st[i] && (t == -1 || dist[t] > dist[i]))
                t = i;
                
        st[t] = true;
        
        for (int i = 1; i <= n; i ++ )
            dist[i] = min(dist[i], dist[t] + g[t][i]);
    }
    
    return dist[ened];
}

堆优化dijkstra

关于堆优化 Dijkstra，就是优化了找最小 dist 点的过程，使用了小根堆进行排序，把原来 \(O(n)\) 的枚举换成 \(O(logm)\) 的排序，从而优化了时间复杂度，也因此堆优化Dijkstra有个\(O(logm)\) 而遍历所有点和边是 \(O(n + m)\) 的，加起来就是 \(O((n+m)logm)\)
小根堆排序，一般用pair存，因为要用 dist 来排序，还要记录这个点的下标，并且pair自带，第一键值优先的排序性质，所以使用。

#define x first
#define y second

typedef pair<int, int> PII;

int dijkstra()
{
    priority_queue<PII, vector<PII>, greater<PII>> q;
    q.push({0, S});
    dist[S] = 0;
    while (q.size())
    {
        auto t = q.top();
        q.pop();
        int ver = t.second, distance = t.first;
        if (st[ver]) continue;
        st[ver] = true;      // 标记已经用这个点更新过了 （此点目前最小）
        
        for (int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > distance + w[i])
            {
                dist[j] = distance + w[i];
                q.push({dist[j], j});
            }
        }
    }
    return dist[T];
}

扩展

虽然是最短路算法，但是算单源最长路也是可以的，证明和上面类似