数据结构与算法 - 最短路径

发表于 更新于 分类于

图的最短路算法有很多，在此记录一下非常常用的四个算法

  • 单源最短路：
    • 不带负权边：Dijkstra
    • 带负权边：Bellman-Ford、SPFA
  • 多源最短路：
    • 适用于正负权边：Floyd（但不能有负环）

743. 网络延迟时间

题目链接：https://leetcode-cn.com/problems/network-delay-time/

有 n 个网络节点，标记为 1 到 n。

给你一个列表 times，表示信号经过 有向 边的传递时间。times[i] = (ui, vi, wi)，其中 ui 是源节点，vi 是目标节点，wi 是一个信号从源节点传递到目标节点的时间。

现在，从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1 。

示例：

743. 网络延迟时间 
输入：times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
输出：2

Bellman-Ford 算法

支持负权。能找到某个结点出发到所有结点的最短路，或者报告某些最短路不存在。

SPFA 算法就是 Bellman-Ford 算法的一种实现。

代码实现：

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        vector<int> distance(n + 1, INT_MAX / 2);
        distance[k] = 0;
        for (int t = 0; t < n; t++) {
            vector<int> relax = distance;
            for (auto& time : times) {
                relax[time[1]] = min(relax[time[1]], distance[time[0]] + time[2]);
            }
            distance = relax;
        }
        int res = *max_element(distance.begin() + 1, distance.end());
        return res == INT_MAX / 2 ? -1 : res;
    }
};

运行结果：

Accepted
52/52 cases passed (248 ms)
Your runtime beats 24.45 % of cpp submissions
Your memory usage beats 45.09 % of cpp submissions (36.2 MB)

队列优化：SPFA

即 Shortest Path Faster Algorithm，很显然，只有上一次被松弛的结点所连接的边，才有可能引起下一次的松弛操作。

那么我们用队列来维护哪些结点可能会引起松弛操作，就能只访问必要的边了。

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        // 1. 建图 存储方式：邻接表（索引方式）
        vector<vector<int>> edges(n + 1);
        for (int i = 0; i < times.size(); i++) {
            edges[times[i][0]].push_back(i);
        }
        // 2. 通过队列来判断哪些结点需要更新
        vector<int> distance(n + 1, INT_MAX / 2);
        distance[k] = 0;
        queue<int> q;
        vector<bool> in_queue(n, false);
        q.push(k);
        in_queue[k] = true;
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            in_queue[u] = false;
            for (auto& index : edges[u]) {
                int v = times[index][1], w = times[index][2];
                if (distance[v] > distance[u] + w) {
                    distance[v] = distance[u] + w;
                    if (!in_queue[v]) {
                        q.push(v);
                        in_queue[v] = true;
                    }
                }
            }
        }
        int res = *max_element(distance.begin() + 1, distance.end());
        return res == INT_MAX / 2 ? -1 : res;
    }
};

运行结果：

Accepted
52/52 cases passed (128 ms)
Your runtime beats 89.48 % of cpp submissions
Your memory usage beats 32.26 % of cpp submissions (37.6 MB)

Dijkstra 算法

这种算法只适用于非负权图，但是时间复杂度非常优秀。是可以用来求单源最短路径的算法。

代码实现：

struct Target {
    int pos;
    int time;
    Target(int p = 0, int t = 0) : pos(p), time(t) {}
    bool operator<(const Target& a) const { return time > a.time; }
};
class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        vector<vector<int>> edges(n + 1);
        for (int i = 0; i < times.size(); i++) {
            edges[times[i][0]].push_back(i);
        }
        priority_queue<Target> Q;
        vector<int> cost(n + 1, INT_MAX);
        vector<int> visited(n + 1, 0);
        Q.push(Target{k, 0});

        while (!Q.empty()) {
            Target t = Q.top();
            Q.pop();
            if (!visited[t.pos]) {
                cost[t.pos] = t.time;
                for (auto& index : edges[t.pos]) {
                    if (!visited[times[index][1]]) {
                        Q.push(Target{times[index][1], times[index][2] + t.time});
                    }
                }
                visited[t.pos] = 1;
            }
        }
        int res = *max_element(cost.begin() + 1, cost.end());
        return res == INT_MAX ? -1 : res;
    }
};

运行结果：

Accepted
52/52 cases passed (164 ms)
Your runtime beats 61.02 % of cpp submissions
Your memory usage beats 31.36 % of cpp submissions (38.7 MB)

Floyd 算法

本质是动态规划，能解决任意两点间的最短路径，时间复杂度 O(V^3)

主要算法思想如下：

for (k = 0; k < n; k++) {
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            // i 到 j 的最短路径 = i 到 k 的最短路径 + k 到 j 的最短路径
            // 当然 要取较小值
            f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
        }
    }
}

代码实现：

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        vector<vector<int>> cost(n, vector<int>(n, INT_MAX / 2));
        for (int i = 0; i < n; i++) cost[i][i] = 0;
        for (auto& t : times) cost[t[0] - 1][t[1] - 1] = t[2];
        for (int m = 0; m < n; m++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    cost[i][j] = min(cost[i][j], cost[i][m] + cost[m][j]);
                }
            }
        }
        int res = *max_element(cost[k - 1].begin(), cost[k - 1].end());
        return res == INT_MAX / 2 ? -1 : res;
    }
};

运行结果：

Accepted
52/52 cases passed (240 ms)
Your runtime beats 26.05 % of cpp submissions
Your memory usage beats 40.68 % of cpp submissions (36.4 MB)

参考资料