Leetcode中的Dijkstra

2023-10-08 17:48:10

根据这个贴: Please Share dijkstra's algorithm questions
Graph - Dijkstra's4926 views

The Maze III
The Maze II
Network Delay Time
Cheapest Flights Within K Stops
Reachable Nodes In Subdivided Graph
Path with Maximum Probability
Find the City With the Smallest Number of Neighbors at a Threshold Distance
Minimum Cost to Make at Least One Valid Path in a Grid
Path With Minimum Effort
Number of Restricted Paths From First to Last Node

0. 变形题：边权为1~5

先介绍一道变形题，感觉还挺有意思的，来自题目求助｜【求助】如何用线性时间复杂度解决单源最短路径问题(详情请看原文)
题目：
Develop a linear-time (i.e., O(m + n)-time) algorithm that solves the Single Source Shortest Path problem for graphs whose edge weights are positive integers bounded by 5. (Hint. You can either modify Dijstra’s algorithm or consider using Breath-First-Search.)

方法：贴下已经有大佬提供的思路了，我实现了一下
边权受限的话可以用桶代替 \(dijkstra\) 算法里的堆。
开一个 \(5n+1\) 大小的数组作桶，一开始把起点放入 \(0\) 号桶，之后遍历桶，碰到桶里有节点，就把节点拿出来更新与这个点相邻的点的距离，更新了的节点再放入新的桶，由于 \(dijkstra\) 算法的距离不减，因此更新的节点一定不会放到已经遍历过的桶里，复杂度 \(O(∣V∣+∣E∣)\)，是线性的。
而且上述解法对于边权很大的情况也能用，把桶的大小从原来的全是 \(1\) 调整为按指数增长即可，这个算法叫做基数堆，时间复杂度多一个 \(\log\)。

实现：

点击查看代码

#include<iostream>
#include<vector>
#include<queue>
using namespace std;

struct Node
{
    int v, d;            //该节点的编号与距离
};

void dijkstra(vector<vector<Node>>& graph, int start, int end, vector<int>& dist) {
    dist[start] = 0;
    // priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    int n = graph.size();
    vector<int> q[5*n+1];  // 长度为5*n+1的数组，用于代替优先队列(相同最小距离的节点可能有多个)
    q[0].push_back(start);
    int i = 0;
    while (i < 5*n+1) {
        cout << "i = " << i << endl;

        vector<int> us = q[i];i++;
        if(us.size() == 0) continue;
        // if(u == end) break;

        for(int u : us) {
            if(dist[u] < i-1) continue;   // 之前已经求得了，但是可能出现在当前位置的列表中
            dist[u] = i-1;

            for(auto& node : graph[u]) {
                int v = node.v, d = node.d;
                if(dist[v] > dist[u] + d) {
                    dist[v] = dist[u] + d;
                    q[dist[v]].push_back(v);
                }
            }

            for(int j = 0;j < 5*n+1;j++) {
                if(q[j].size() > 0) {
                    for(int k = 0;k < q[j].size();k++) {
                        char ch = k == q[j].size()-1 ? ' ' : ',';
                        cout << q[j][k] << ch;
                    }
                } else {
                    cout << 0 << " ";
                }
                
            }
            cout << endl;
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<Node>> graph(n+1);
    for(int i = 0; i < m; i++) {
        int u, v, d;
        cin >> u >> v >> d;
        graph[u].push_back({v, d});
        graph[v].push_back({u, d});
    }
    vector<int> dist(n+1, INT_MAX);
    dijkstra(graph, 1, n, dist);
    for(int i = 1; i <= n; i++) {
        cout << i << ": " << dist[i] << endl;
    }
    // cout << dist[n] << endl;
    return 0;
}

注意由于同一位置(也就是同一距离)可以对应多个节点，应该用个vector来表示桶

码农公寓

0. 变形题：边权为1~5

相关文章