最短路径问题

在一个图中有 n 个点、m 条边。边有权值，例如费用、长度等，权值可正可负。边可能是有向的，也可能是无向的。给定两个点，起点是 s，终点是 t，在所有能连接 s 和 t 的路径中寻找边的权值之和最小的路径，这就是最短路径问题。
注：若图中存在负圈，则不存在最短路问题，若存在负边权，则不能用 Dijkstra算法。

Floyd-Warshall 算法

算法复杂度： $图片说明$
Floyd 用到了动态规划的思想：求两点 i、j 之间的最短距离，可以分两种情况考虑，即经过图中某个点 k 的路径和不经过点 k 的路径，取两者中的最短路径。注：有重边要在输入的时候更新最小值。

const int maxn = 1e4+1;
const int inf = 0x3f3f3f3f;
int graph[maxn][maxn];

void init(int n) {
    for(int i = 1; i <= n; ++ i) {
        for(int j = 1; j <= n; ++ j) {
            if (i == j) graph[i][j] = 0;
            else graph[i][j] = inf;
        }
    }
}

void Floyd(int n) { // 传递闭包
    for(int k = 1; k <= n; ++ k) { // dp 是否过 k 点
        for(int i = 1; i <= n; ++ i) {
            for(int j = 1; j <= n; ++ j) {
                graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);
            }
        }
    }
}

Bellman-Ford 算法

时间复杂度： $图片说明$
Bellmen-Ford 算法用来解决单源最短路径问题：给定一个起点 s，求它到图中所有 n 个节点的最短路径。
Bellmen-Ford 算法的特点是只对相邻节点进行计算，可以避免 Floyd 那种大撒网式的无效计算，大大提高了效率，每次操作必定确定一个点的最短路。
注：可打印最短路径，可判断负圈

const int maxn = 1e4+1;
const int inf = 0x3f3f3f3f;
int d[maxn], pre[maxn];

struct edge{
    int u, v, w;
    edge(){};
    edge(int u, int v, int w): u(u), v(v), w(w){};
}e[maxn]; int tot; // tot 注意清空

void print_path(int st, int en){ // 打印从 st 到 en 的最短路
    if (st == en) {printf("%d", st); return ;}
    print_path(st, pre[en]);  // en 点向前搭载
    printf("->%d", en);
}

void Bellman(int st, int n) { // st 的单源最短路
    for(int i = 1; i <= n; ++ i) {
        if (i == st) d[i] = 0;     // 定义起点
        else d[i] = inf;
    }
    int k = 0;        // 记录几次操作 没有负圈最多 n-1 次操作
    bool update = true;
    while(update) {
        update = false;
        if (++ k > n) {printf("有负圈\n"); return ;}   // 第n次操作成功，有负圈
        for(int i = 1; i <= tot; ++ i) {               // 搭载每条边
            int x = e[i].u, y = e[i].v;
            if (d[x] > d[y] + e[i].w) { // 更新最短路
                update = true;
                d[x] = d[y] + e[i].w;
                pre[x] = y;         // 记录前驱点
            }
        }
    }
}

SPFA 算法

时间复杂度： $图片说明$
Bellman-Ford 算法有很多低效或无效的操作。分析 Bellman-Ford 算法，其核心部分是在每一***作中更新所有节点到起点 s 的最短距离。根据前面的讨论可知，计算和调整一个节点 u 到 s 的最短距离之后，如果紧接着调整 u 到邻居结点，这些邻居肯定有新的计算结果；而如果漫无目的的计算不与 u 相邻的节点，很可能毫无变换，所以这些操作是低效的。
因此，在计算结点 u 之后，下一步只计算和调整特的邻居，这样能加快收敛过程。这些步骤可以用队列进行操作，这就是 SPFA（很像 BFS）。

const int maxn = 1e6+1;
const int inf = 0x3f3f3f3f;
int dis[maxn];  // 存储最短路
int pre[maxn];  // 存储路径
int Neg[maxn];  // 存储点已遍历次数
bool vis[maxn]; // 判断点是否在队内

struct edge { // 邻接表
    int to, w;
    edge(){}
    edge(int to, int w): to(to), w(w){}
}; vector<edge> g[maxn];

void init(int n) { // 多实例初始化
    for(int i = 1; i <= n; ++ i) {
        g[i].clear();
    }
}

void print_path(int st, int en){ // 打印从 st 到 en 的最短路
    if (st == en) {printf("%d", st); return ;}
    print_path(st, pre[en]);  // en 点向前搭载
    printf("->%d", en);
}

void Spfa(int st, int n) { // SPFA 算法 - 求单源最短路
    for(int i = 1; i <= n; ++ i) { // 算法初始化
        Neg[i] = 0;
        dis[i] = inf;
        vis[i] = false;
    }
    queue<int> q;
    q.push(st);
    Neg[st] = 1;
    dis[st] = 0;
    vis[st] = true;
    while(!q.empty()) {
        int tp = q.front(); q.pop();
        vis[tp] = false;
        for(auto t: g[tp]) {
            int to = t.to;
            if (dis[to] > dis[tp] + t.w) {    // 更新最短路
                dis[to] = dis[tp] + t.w;
                pre[to] = tp;                     // 记录前驱点
                if (!vis[to]) { // to 点进入更新状态
                    q.push(to);
                    vis[to] = true;
                    if (++Neg[to] > n) {printf("有负圈\n"); return ;}  // 第n次操作成功，有负圈
                }
            }
        }
    }
}

Dijstra 算法

时间复杂度 $图片说明$
Dijkstra 算法也用来解决单源最短路径问题(无法解决有负边权的图)。
在现实生活中，Dijkstra 有另外的模型，例如多米诺骨牌：

在图中所有的边上排满多米诺骨牌，相当于把骨牌看成图的边。一条边上的多米诺骨牌数量和边的权值（例如长度或费用）成正比。规定所有的骨牌倒下的速度都是一样的。如果在一个结点上推到骨牌，会导致这个结点上的所有骨牌都往后面倒去。
在起点 s 推到骨牌，可以观察到，从 s 开始，它连接的边上的骨牌都逐渐倒下，并到达所有能达到的结点。在某结点 t，可能先后从不同的线路倒骨牌过去；先倒过来的骨牌，其经过的路径肯定就是从 s 到 t 的最短路径；后倒过来的骨牌，对确定结点 t 的最短路径没有贡献，不用管它。

注：在程序中不可能随着时间的变化去模拟一遍上述过程，那就用优先队列做一个处理，保证在堆顶的结点一定是时间最短的，通过不断松弛其他点，加入队堆可以更新最短路。

const int maxn = 1e6+1;
const int inf = 0x3f3f3f3f;

struct edge{ // 链式前向星
    int to, next, w;
    edge(){}
    edge(int to, int next, int w): to(to), next(next), w(w){}
}e[maxn]; int head[maxn], tot;

struct node{
    int id, dis;
    node(){}
    node(int id, int dis): id(id), dis(dis) {}
    bool operator> (const node &n1) const { // 小顶堆需重载 >
        return dis > n1.dis;
    }
}pos[maxn];

int pre[maxn];   // 存储路径
bool vis[maxn];  // 是否已得出最短路

void init(int n) { // 多实例初始化
    tot = 0;
    for(int i = 1; i <= n; ++ i) {
        head[i] = -1;
    }
}

void print_path(int st, int en) { // 打印从 st 到 en 的最短路径
    if (st == en) {printf("%d", st); return ;}
    print_path(st, pre[en]); // en 点向前搭载
    printf("->%d", en);
}

void Dijkstra(int st, int n) { // Dijkstra 算法 - 单源最短路
    for(int i = 1; i <= n; ++ i) { // 算法初始化
        pos[i].id = i;
        pos[i].dis = inf;
        vis[i] = false;
    }
    pos[st].dis = 0;
    priority_queue<node, vector<node>, greater<node> > q; // 小顶堆
    q.push(pos[st]);
    while(!q.empty()) {
        node tp = q.top(); q.pop();
        if (vis[tp.id]) continue; // 该点最短路已得出 跳过
        vis[tp.id] = true;
        for(int i = head[tp.id]; ~i; i = e[i].next) {
            int to = e[i].to;
            if (vis[to]) continue;
            if (pos[to].dis > tp.dis + e[i].w) { // 松弛操作 无法处理和判断负圈
                pos[to].dis = tp.dis + e[i].w;   // 经过松弛后，同一个点可能会多次存入
                pre[to] = tp.id;                 // 记录前驱点
                q.push(pos[to]);
            }
        }
    }
}

专题

http://acm.hdu.edu.cn/showproblem.php?pid=6797 【最短路 + 随机数据】