Dijkstra算法

发表于 | 分类于 | |
字数统计: 2,035 | 阅读时长 ≈ 10

算法简介

Dijkstra算法是一种计算最短路径的算法，对于给定的一个有权重的图，Dijkstra算法可以计算出任一点到其他各点的最短路径。

Dijkstra‘s algorithm是一种greedy algorithm。贪婪算法就是在算法的每一个阶段都取最大值。一般情况下，贪婪算法能取得较好的效果。但是贪婪算法是有其缺陷的，也就是说能达到局部最优，而未必能达到全局最优，举个例子，假设要兑换15分的硬币，而硬币有12分的，10分的，5分的，1分的，那么根据贪婪算法，最终的兑换结果为1个12分的，3个一分的；而最优结果应该是一个10分的，一个5分的。（这里我们定义最优为硬币个数最少）。

Dijkstra‘s algorithm的步骤是：
对于每一个阶段，Dijkstra‘s algorithm会在所有未处理的点中选取一个最小距离的点v，然后把给定点s到v的路径定义为最小路径。

算法图解原理

假设我们有如下的一个图

我们需要知道v1到其他所有点的最短花费，那么要怎么做呢？

我们需要定义一个distance[]数组用来记录最短的花费
定义一个visited[]数组来记录是否访问过节点

首先选择v1点，然后遍历v1的所有子节点，这里有v2和v4，在distance里面记录他们的距离

【0，2，+oo，1，+oo，+oo，+oo】
【1，0，0，0，0，0，0】

然后选择未遍历的最近的点，就是v4，然后遍历v4的子节点，这里有v3，v6，v7，v5。我们更新v1到这些点的距离

【0，2，3，1，3，9，5】
【1，0，0，1，0，0，0】

然后从未遍历的点中，选择距离最短的点，那就是v2点，然后用v2点来更新最短距离，看v2的子节点v4，v5。然后更新这两个节点的最小距离
我们发现通过v2点的距离分别为5和12，这大于已有的最短距离，因此不更新distance中的数据

【0，2，3，1，3，9，5】
【1，1，0，1，0，0，0】

然后选择下一个节点v3，它的子节点v1和v6，v1不需要更新，那我们看v6，通过v3点的距离为3 + 5 = 8 < 9，因此需要更新v6的最短距离

【0，2，3，1，3，8，5】
【1，1，1，1，0，0，0】

然后选择下一个节点v5，它的子节点为v7，通过v5的距离 3 + 6 = 9 > 5，因此不更新distance中的最短距离

【0，2，3，1，3，8，5】
【1，1，1，1，1，0，0】

然后选择下一个节点v7，它的子节点为v6，通过v7到v6的距离为 5 + 1 = 6 < 8，因此更新distance中的最短距离

【0，2，3，1，3，6，5】
【1，1，1，1，1，0，1】

最后剩下一个节点v6，他没有子节点，结束。

算法实现

  • 首先定义数据结构，以点为中心

    1
    2
    3
    4
    vector<vector<vector<int>>> graphs;
    graphs[0]表示点0对应的边信息
    graphs[0][0]表示点0对应的第一条边的信息
    graphs[0][0]包含三个元素，分别为启示点，终点，以及权重。

  • 再定义一个distance的数组，因为每次要取最小的值，因此最好用priority_queue。

  • 还要定义一个结构用来对应节点和最小的值，以及是否被访问过

    1
    2
    3
    4
    5
    struct Node {
        int nodeId;
        int distance;
        bool isVisited;
    }

下面我们来看具体的实现：

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
typedef struct Node {
    int nodeId;
    int distance;
    bool isVisited;
    bool operator<(const Node& rhs) const {
        return distance < rhs.distance;
    }
} Node;

priority_queue<struct Node> pq;

vector<int> distanceVec;

vector<int> Dijkstra(vector<vector<vector<int>>>& graphs)
{
    vector<Node> nodeVec(graphs.size());
    distanceVec.resize(graphs.size(), INT_MAX);
    for (int i = 0; i < graphs.size(); ++i) {
        nodeVec[i].distance = INT_MAX;
        nodeVec[i].nodeId = i;
        nodeVec[i].isVisited = false;
    }
    nodeVec[k - 1].distance = 0;
    pq.push(nodeVec[k - 1]);
    while (!pq.empty()) {
        Node curr = pq.top();
        pq.pop();
        
        if (nodeVec[curr.nodeId].isVisited) {
            continue;
        }
        
        nodeVec[curr.nodeId].isVisited = true;
        for (auto& edge : graphs[curr.nodeId]) {
            int to = edge[1];
            int weight = edge[2];
            if (nodeVec[to].isVisited) {
                continue;
            }
            int currDistance = curr.distance + weight;
            if (nodeVec[to].distance > currDistance) {
                nodeVec[to].distance = currDistance;
                distanceVec[to] = currDistance;
                pq.push(nodeVec[to]);
            }
        }
    }
}

例题分析

743. 网络延迟时间

这个问题就是一个标准的Dijkstra算法的应用。在这道题目中，我们需要计算出起始节点到所有节点的距离，然后从结果中选择最大值即可。

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
typedef struct Node {
    int nodeId;
    int distance;
    bool isVisited = false;
    bool operator<(const Node& rhs) const {
        return distance < rhs.distance;
    }
} Node;

priority_queue<struct Node> pq;

vector<int> distanceVec;

class Solution {
public:
    // 根据题目的数据，构建图的数据结构
    vector<vector<vector<int>>> buildGraph(vector<vector<int>>& times, int n)
    {
        vector<vector<vector<int>>> graphs;
        graphs.resize(n);
        for (auto& time : times) {
            int from = time[0] - 1;
            int to = time[1] - 1;
            int weight = time[2];
            graphs[from].push_back({from, to, weight});
        }
        return graphs;
    }

    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        distanceVec.clear();
        while (!pq.empty()) {
            pq.pop();
        }

        vector<vector<vector<int>>> graphs = buildGraph(times, n);
        // 初始化所有的节点结构
        vector<Node> nodeVec(graphs.size());
        distanceVec.resize(graphs.size(), INT_MAX);
        for (int i = 0; i < graphs.size(); ++i) {
            nodeVec[i].distance = INT_MAX;
            nodeVec[i].nodeId = i;
            nodeVec[i].isVisited = false;
        }
        // 开始遍历
        nodeVec[k - 1].distance = 0;
        pq.push(nodeVec[k - 1]);
        while (!pq.empty()) {
            Node curr = pq.top();
            pq.pop();
            
            if (nodeVec[curr.nodeId].isVisited) {
                continue;
            }
            
            nodeVec[curr.nodeId].isVisited = true;
            for (auto& edge : graphs[curr.nodeId]) {
                int to = edge[1];
                int weight = edge[2];
                if (nodeVec[to].isVisited) {
                    continue;
                }
                int currDistance = curr.distance + weight;
                if (nodeVec[to].distance > currDistance) {
                    nodeVec[to].distance = currDistance;
                    distanceVec[to] = currDistance;
                    pq.push(nodeVec[to]);
                }
            }
        }

        int maxValue = 0;
        for (int i = 0; i < n; ++i) {
            if (i == k -1) {
                continue;
            }
            maxValue = max(maxValue, distanceVec[i]);
        }
        return maxValue == INT_MAX ? -1 : maxValue;
    }
};

1631. 最小体力消耗路径

1514. 概率最大的路径

这道题目初看好像跟Dijkstra关系不大，首先这是个无向图，其次这次是各个路径相乘，而且是最大值。实际上这也是可以用Dijkstra算法的，只不过是要做一定的修改变通。

  • 首先无向图实际上就是一个双向的有向图罢了
  • 其次每次更新的时候，把加法换做乘法即可，同时大值才更新
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
58
59
60
61
62
63
64
65
66
67
68
69
typedef struct Node {
    double nodeId;
    double weight;
    bool isVisited = false;
    bool operator<(const Node& rhs) const {
        return weight < rhs.weight;
    }
} Node;

class Solution {
public:
    vector<vector<vector<double>>> buildGraph(int n, vector<vector<int>>& edges, vector<double>& succProb)
    {
        vector<vector<vector<double>>> graphs(n);
        for (int i = 0; i < edges.size(); ++i) {
            double from = edges[i][0];
            double to = edges[i][1];
            double weight = succProb[i];
            graphs[from].push_back({from ,to, weight});
            graphs[to].push_back({to, from ,weight});
        }
        return graphs;
    }
    double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start, int end) {
        vector<vector<vector<double>>> graphs = buildGraph(n, edges, succProb);

        vector<Node> nodeVec(n);
        for (int i = 0; i < n; ++i) {
            nodeVec[i].weight = 0.0f;
            nodeVec[i].nodeId = i;
            nodeVec[i].isVisited = false;
        }


        nodeVec[start].weight = 1.0f;
        pq.push(nodeVec[start]);
        while (!pq.empty()) {
            Node curr = pq.top();
            pq.pop();
            
            // 提前结束
            if (curr.nodeId == end) {
                return nodeVec[end].weight;
            }
            
            if (nodeVec[curr.nodeId].isVisited) {
                continue;
            }
            
            nodeVec[curr.nodeId].isVisited = true;
            int currNodeId = static_cast<int>(curr.nodeId);
            for (auto& edge : graphs[currNodeId]) {
                int to = static_cast<int>(edge[1]);
                double weight = edge[2];
                if (nodeVec[to].isVisited) {
                    continue;
                }
                double currWeight = curr.weight * weight;
                if (currWeight > nodeVec[to].weight) {
                    nodeVec[to].weight = currWeight;
                    pq.push(nodeVec[to]);
                }
            }
        }
        return nodeVec[end].weight;
    }
private:
    priority_queue<Node> pq;
};

扩展

从上面的算法可以看出，Dijkstra算法适合于计算权重为正的有向图。

  • 那么如果权重为负呢？Dijkstra算法无法直接解决权重为负的图，但是我们可以为所以的权重都加一个正数，让权重变为正，就可以解决了
  • 如果是无权重图呢？更简单了，那就相当于所有的权重均为1。

因此对于有向图，一般都可以通过Dijkstra算法来解决最短路径问题

显示 Gitment 评论