leetcode 图的最短路径问题 优先队列实现dijkstra算法（743、787、1334）_图的最短路径 leetcode

743 网络延迟时间

题目描述： 有 N 个网络节点，标记为 1 到 N。给定一个列表 times，表示信号经过有向边的传递时间。 times[i] = (u, v, w)，其中 u 是源节点，v 是目标节点， w 是一个信号从源节点传递到目标节点的时间。
现在，我们向当前的节点 K 发送了一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1。
注意： N 的范围在 [1, 100] 之间。
K 的范围在 [1, N] 之间。
times 的长度在 [1, 6000] 之间。
所有的边 times[i] = (u, v, w) 都有 1 <= u, v <= N 且 0 <= w <= 100。
思路： 题目可以转化为求解在一个带权有向图中给定顶点到任意一个顶点最短路径的最大值。由于所有的权重值都为正数，所以可以考虑用dijkstra算法求解。具体思路见代码中注释。

// 优先队列 dijkstra算法（用优先队列可以优化dijkstra）
class node {
// node节点中存放图中每个顶点的id以及该顶点到达出发顶点的距离
// 该距离未必是最终的最小距离
    public:
        int id;
        int dis;
        friend bool operator < (const node x, const node y) {  // 重载优先队列的排序规则，dis小的先出队列 
            return x.dis > y.dis;
        }
};
class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int N, int K) {
        int ans = 0;
        int cnt = 0;
        vector<vector<node>> edges(N + 1); // 构造图
        for(int i = 0; i < times.size(); i++) { //存储每个点的邻接顶点信息
            edges[times[i][0]].push_back(node{times[i][1], times[i][2]});
        }
        vector<int> vis(N + 1, -1); // 存储每个点到出发顶点的最短距离 该距离不断更新变小
        priority_queue<node> Q; // 用优先队列实现dijkstra
        Q.push(node{K, 0}); // 压入出发顶点
        vis[K] = 0;
        while(!Q.empty()) {
            node u = Q.top();
            Q.pop();
            if(u.dis > vis[u.id]) // 剪枝 根据优先队列的出栈规则，dis值小的先出栈，并且vis数组中始终更新为最小的距离，一旦u.dis > vis[u.id]，则说明u.id这个顶点第二次出栈，dis值也更大，此时cnt不累加，直接pop下一个node。
                continue;
            cnt++;
            //cout<< cnt<<endl;
            ans = max(ans, u.dis); // 不断更新答案的最大值
            for(int i = 0; i < edges[u.id].size(); i++) {
                int v = edges[u.id][i].id;
                if(vis[v] == -1 || vis[v] > edges[u.id][i].dis + u.dis) {
                    vis[v] = edges[u.id][i].dis + u.dis; // 更新vis数组
                    Q.push(node{v, vis[v]});
                }
            }
        }
        if(cnt < N)
            return -1;
        return ans;
    }
};
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
39
40
41
42
43
44
45

787 K站中转内最便宜的航班

题目描述： 有 n 个城市通过 m 个航班连接。每个航班都从城市 u 开始，以价格 w 抵达 v。现在给定所有的城市和航班，以及出发城市 src 和目的地 dst，你的任务是找到从 src 到 dst 最多经过 k 站中转的最便宜的价格。 如果没有这样的路线，则输出 -1。
注意： n 范围是 [1, 100]，城市标签从 0 到 n - 1.
航班数量范围是 [0, n * (n - 1) / 2].
每个航班的格式 (src, dst, price).
每个航班的价格范围是 [1, 10000].
k 范围是 [0, n - 1].
航班没有重复，且不存在环路.
思路1： 优先队列实现dijkstra。基本思路同上一题。但是增加了一个条件： 最多经过 k 站中转。 即要同时考虑最短距离以及中转站数目。出发顶点至到达顶点的所有路径中，可能存在的每一种小于数目K的中转站数目（0,1···k-1,k）都有对应的最短距离，这些最短距离并不相同。我们需要求所有从出发顶点开始，满足中转站小于等于K的最短距离中的最小值。具体思路见代码。
思路2： 动态规划。具体思路见注释。

// 优先队列实现Dijkstra算法
class node {
    public:
        int id;
        int dis;
        int cnt; // 中转
        friend bool operator < (const node a, const node b) {
            return a.dis > b. dis; 
        }
};
class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
        vector<vector<node>> edges(n);
        for(int i = 0; i < flights.size(); i++) {
            edges[flights[i][0]].push_back(node{flights[i][1], flights[i][2], -1});
        }
        vector<vector<int>> vis(K + 2, vector<int>(n, -1));
        priority_queue<node> Q;
        Q.push(node{src, 0, 0});
        vis[0][src] = 0; // 二维矩阵 第一维为中转数目，第二维为顶点id
        while(!Q.empty()) {
            node q = Q.top();
            Q.pop();
            cout<<q.id<<" "<<q.dis<<" "<<q.cnt<<endl;
            if(q.dis > vis[q.cnt][q.id]) // 如果大于 则说明最短距离的node节点已经出栈
                continue;
            if(q.id == dst && q.cnt <= K + 1)
                return q.dis;
            if(q.cnt == K+1) // 剪枝
                continue;
            for(int i = 0; i < edges[q.id].size(); i++) {
                int v = edges[q.id][i].id;
                if(vis[q.cnt + 1][v] == -1 || vis[q.cnt + 1][v] > q.dis + edges[q.id][i].dis) {
                    vis[q.cnt + 1][v] = q.dis + edges[q.id][i].dis;
                    Q.push(node{v, q.dis + edges[q.id][i].dis, q.cnt + 1});
                }
            }
        }
        return -1;
    }
};
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
39
40
41
42

// 思路2 DP
class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
        // 动态规划 dp[k][i] 表示经过k - 1站中转到达城市i的最便宜价格
        // dp[k][i]不断更新 最终表示在所有到达城市i的中转站数目小于等于k - 1的方案中 最便宜价格
        // 出发点中转站数目不能为-1 设为0
        int kInfCost = 1e9;
        vector<vector<int>> dp(K + 2, vector<int>(n, kInfCost));
        dp[0][src] = 0;
        for(int i = 1; i < K + 2; i++) {
            dp[i][src] = 0; // 为了能和中转站数小于i的路线花费相比较
            for(auto& p : flights) 
                dp[i][p[1]] = min(dp[i][p[1]], dp[i - 1][p[0]] + p[2]);
        }
        return (dp[K + 1][dst] == kInfCost ? -1 : dp[K + 1][dst]);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

1334 阈值距离内邻居最少的城市

题目描述： 有 n 个城市，按从 0 到 n-1 编号。给你一个边数组 edges，其中 edges[i] = [fromi, toi, weighti] 代表 fromi 和 toi 两个城市之间的双向加权边，距离阈值是一个整数 distanceThreshold。
返回能通过某些路径到达其他城市数目最少、且路径距离最大为 distanceThreshold 的城市。如果有多个这样的城市，则返回编号最大的城市。注意，连接城市 i 和 j 的路径的距离等于沿该路径的所有边的权重之和。
说明： 2 <= n <= 100
1 <= edges.length <= n * (n - 1) / 2
edges[i].length == 3
0 <= fromi < toi < n
1 <= weighti, distanceThreshold <= 10^4
所有 (fromi, toi) 都是不同的。
思路： 优先队列实现dijkstra。思路同743题，但是要遍历每一个顶点，将每一个顶点都当做出发顶点，统计每一个顶点小于阈值距离的邻居数目。具体实现细节见代码注释。

// 同743题 优先队列实现dijkstra
class node {
    public:
        int id;
        int dis;
        friend bool operator < (const node x, const node y) { // 自定义优先队列中的排序方式
            return x.dis > y.dis; // 优先队列默认从大到小，重载后，变为从小到大。
        }
};
class Solution {
public:
    // start为开始节点，优先队列中最小的超过distanceThreshold就直接return就好了
    // 返回有多少个城市小于等于distanceThreshold
    int dijkstra(vector<int> &dis, vector<vector<node>> &edges, int start, int distanceThreshold) {
        priority_queue<node> Q;
        Q.push(node{start, 0});
        dis[start] = 0;
        int cnt = 0;
        while(!Q.empty()) {
            node u = Q.top();
            Q.pop();
            // 剪枝
            if(u.dis > distanceThreshold) // 由于是优先队列 一旦出队列的距离开始大于阈值，那之后出队列的距离肯定也大于阈值
                return cnt;
            if(u.dis > dis[u.id]) // 顶点距离会更新 由于是优先队列，被更新的距离肯定晚于更新后的距离出队列，同一个顶点第一次出队列对应的距离为最短距离，只有这时才cnt++
                continue;
            cnt += 1;
            for(int i = 0; i < edges[u.id].size(); i++) {
                int v = edges[u.id][i].id;
                if(dis[v] == -1 || dis[v] > edges[u.id][i].dis + u.dis) {
                    dis[v] = edges[u.id][i].dis + u.dis;
                    Q.push(node{v, dis[v]});
                }
            }
        }
        return cnt;
    }

    int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {
        vector<vector<node>> e(n);
        for(int i = 0; i < edges.size(); i++) {
            e[edges[i][0]].push_back(node{edges[i][1], edges[i][2]});
            e[edges[i][1]].push_back(node{edges[i][0], edges[i][2]});
        }
        int ans = 0, cnt_city = n;
        for(int i=0; i<n; i++) {
            vector<int> dis(n, -1);
            int cnt = dijkstra(dis, e, i, distanceThreshold);
            // cout << i << " " << cnt << endl;
            if(cnt <= cnt_city) {
                cnt_city = cnt;
                ans = i;
            }
        }
        return ans;
    }
};
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57