最短路

发表于 | 分类于 | | 阅读次数:
字数统计: 903 | 阅读时长 ≈ 4

简介

所谓最短路问题，就是求两节点间权值和最小的路径。
在一张图中，不一定存在最短路径，也不一定只存在唯一的最短路径。

代码

最短路算法主要有三种：Floyd、Dijkstra和SPFA，其中SPFA基于Bellman-Ford算法。
关于这三种算法的优劣，可见下表：

算法 Floyd Dijkstra SPFA
适用范围 无负环图 非负权图 任意图
时间复杂度 $O(n^{3})$ $O((n + m) \log n)$ $O(m)$，最坏$O(n m)$

Floyd

Floyd算法采用了DP思想，简洁易写（然而效率不是很高）。

用$f_{i, j, k}$表示从点$i$到点$j$，仅通过编号为$1 - k$的节点的最短距离，那么容易得出：

初始值$f_{i, j, 0}$为两点间的边权值，若未连通则为INF。
从$1 - n$枚举$k$，然后枚举$i, j$即可。三重循环暴力解决。

我们发现第三维完全可以省去，于是代码是这样的：

1
2
3
4
5
6
7
8
int f[MAX_SIZE][MAX_SIZE];
void floyd() {
    for (int k = 1; k <= n; ++k)
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                if (i != j && i != k && j != k)
                    f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
}

Dijkstra

Dijkstra的主要思想是：
将起点作为已访问集合的第一个点，找到未被访问的$dis$最小的点，标记访问，用这个点更新相邻的点的$dis$。重复上述过程，直到所有点都被访问。

我们可以用小根堆（STL的priority_queue）实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
// 建图
struct Edge {
    int from, to, dis;
    Edge(int _from, int _to, int _dis) {
        from = _from;
        to = _to;
        dis = _dis;
    }
};
std::vector<Edge> g[MAX_SIZE];
void insert(int u, int v, int w) {
    g[u].push_back(Edge(u, v, w));
}
int dis[MAX_SIZE];

int dijkstra(int s, int u) {
    bool vis[MAX_SIZE] = {};
    std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> q;
    memset(dis, 0x3f, sizeof(dis));
    dis[s] = 0;
    q.push(std::make_pair(0, s));
    while (!q.empty()) {
        int now = q.top().second;
        q.pop();
        if (!vis[now]) {
            vis[now] = true;
            for (int i = 0; i < int(g[now].size()); ++i) {
                Edge e = g[now][i];
                if (dis[e.to] > dis[now] + e.dis) {
                    dis[e.to] = dis[now] + e.dis;
                    q.push(std::make_pair(dis[e.to], e.to));
                }
            }
        }
    }
    return dis[u];
}

SPFA

SPFA是Bellman-Ford的队列优化，这种算法基于松弛（relax）操作。
在Bellman-Ford算法中，需要对整张图进行$n - 1$次松弛，每次枚举每条边进行松弛，而SPFA避免了无意义的松弛操作。

SPFA还可以用于判负环，若某个点被relax了$n$次，那么这张图就一定存在负环。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
// 建图
struct Edge {
    int from, to, dis;
    Edge(int _from, int _to, int _dis) {
        from = _from;
        to = _to;
        dis = _dis;
    }
};
std::vector<Edge> g[MAX_SIZE];
void insert(int u, int v, int w) {
    g[u].push_back(Edge(u, v, w));
}
int dis[MAX_SIZE];

int spfa(int s, int u) {
    bool vis[MAX_SIZE] = {};
    std::queue<int> q;
    memset(dis, 0x3f, sizeof(dis));
    dis[s] = 0;
    q.push(s);
    vis[s] = true;
    while (!q.empty()) {
        int now = q.front();
        q.pop();
        for (int i = 0; i < int(g[now].size()); ++i) {
            Edge e = g[now][i];
            if (dis[e.to] > dis[now] + e.dis) {
                dis[e.to] = dis[now] + e.dis;
                if (!vis[e.to]) {
                    q.push(e.to);
                    vis[e.to] = true;
                }
            }
        }
    }
    return dis[u];
}

比赛中非常不建议使用SPFA，因为SPFA很容易被卡。但是它的实现还是有必要学的，处理负边权的题一般SPFA都能过。

例题

0%