图论入门：单源最短路径算法

问题描述：

设有$ n $个点，$ m $条边，源点为$ s $，求出源点到所有点距离的最小值。
输入的第一行为三个数$ n $，$ m $，$ s $，随后的$ m $行每行输入三个数，代表一条边的起始点，终点和长度。

在这里我们统一使用邻接表（链式前向星）存储图，邻接表的定义如下：

struct Edge {
    int des, next, w;
}edges[200000 + 5];
int head[100000 + 5], cnt = 0;

void add_edge( int from, int des, int w ) {
    edges[++cnt].des = des;
    edges[cnt].w = w;
    edges[cnt].next = head[from];
    head[from] = cnt;
}

没有负权值的情况

我们都已经了解了多源最短路算法的Floyd算法（同样适用于有负权值的情况），它的时间复杂度为$ O(n^3) $，对于多源的题目，该复杂度已经难以继续改进了~~（反正我不会）~~，但现在只有一个源点，如果仍然使用floyd算法无疑会造成巨大的时间浪费。

算法一：BFS

BFS算法，也就是广度优先搜索算法，适用于所有边的权值都为1的情况。思想是每一次遍历同一层的所有结点，遍历完成后再遍历下一层的所有结点，算法的时间复杂度为$ O(n) $，由于该算法较为简单，再次不多叙述。

算法二：Dijkstra

由远古大神Dijkstra发明的算法，思想是将点集分为两个集合，一个集合$ S_1 $里的点均已求出到源点的最短距离，另一个$ S_2 $还未求出。每次在$ S_2 $中找到距离 $ s $ 最短的结点，用其对所有与之相连的$ S_2 $中的结点进行“松弛操作”，也就是d[v] = min(d[v], d[u] + w[i])，$ u $为刚刚选取的点，$ v $为与之相连的点，不断进行该操作，直至$ S_2 $为空，即可求出所有点到源点的最短距离。

正确性证明：假设存在一个点 $ t\in S_2 $使得经过 $ t $ 到 $ u $ 的距离比经过$ S_1 $中点到 $ u $ 的距离短，由于不存在负权值的边存在，那么$ S_1 $中点到 $ t $ 的距离一定小于到 $ u $ 的距离，那么此时选取的点应当为 $ t $，于此时选取 $ u $ 矛盾，故算法成立。
时间复杂度：$ O(n^2) $

优化：之前选取的时候，我们采取的是遍历的方法找到距离$ S_1 $中点最近的点，有没有更好的方法呢? 答案是采用优先队列优化，
优化后的时间复杂度降低为 $ O(m\log{n}) $

代码：

typedef pair<int, int> P;

int d[100000 + 5];
priority_queue<P, vector<P>, greater<P>> q;

void dijkstra(int s) {
    d[s] = 0; q.push( P(0, s) );
    while (!q.empty()) {
        P t = q.top(); q.pop();
        int u = t.second;
        if ( d[u] < t.first ) continue;
        for (int i = head[u]; i; i = edges[i].next ) {
            int v = edges[i].des;
            int w = edges[i].w;
            if (d[u] + w < d[v]) {
                d[v] = d[u] + w;
                q.push( P(d[v], v) );
            }
        }
    }
}

dijkstra算法非常重要，在没有负权值的情况下速度非常快，强烈建议掌握。

有负权值的情况

有负权值存在时，就可能出现一种情况，一个圈的权值之和为负数。那么如果沿着这个圈一直走，权值便会一直减小，无穷无尽。所以需要单独判断。

算法：Bellman-Ford / spfa:

我们采取的算法为优化后的Bellman-Ford算法，在国内也被称为spfa算法。思想是每次从队列取出一个结点，用该结点对所有与之相连的不在队列中的点做松弛操作，并将其入队，同时记录下每一个结点入队的次数，可以证明，一个结点最多入队 $ n - 1 $ 次，否则找到了负环，可直接跳出循环。
时间复杂度很迷，大概是介于$ O(n^2) $和 $ O(mn) $之间。

代码：

int n, m, s;
int d[ maxn ], Eqtime[ maxn ], p[ maxn ];
bool Enqueue[ maxn ] {false}, flag = false;
int rear = 0;

void bellman_ford( int s ) {
    queue< int > q;
    d[s] = 0; q.push(s);
    Enqueue[s] = true; Eqtime[s]++;
    while(!q.empty()) {
        int u = q.front(); q.pop(); Enqueue[u] = false;
        for (int i = head[u]; i; i = edges[i].next) {
            int v = edges[i].des;
            int w = edges[i].w;
            if (d[u] + w < d[v]) {
                d[v] = d[u] + w; p[v] = w;
                if (Enqueue[v] == false) {
                    if (Eqtime[v] == n) { flag = true; break; }
                    Enqueue[v] = true;
                    Eqtime[v]++; q.push(v);
                }
            }
        }
        if(flag) break;
    } 
}