Dijkstra 最短路径算法

发表于 分类于 ， 阅读次数： Waline： 本文字数： 10k 阅读时长 ≈ 9 分钟

Dijkstra思想

前面我们讲图的遍历的时候讲过，图的存储主要就是邻接矩阵和邻接表。

我们知道广度优先搜索(BFS)也可以查找最短路径，但是却只能针对无权图。

最短路径：带权路径长度最短的那条路就是最短路径。

带权有向图的最短路径问题可以分为两类：一是单源最短路径，即求图中某一顶点到其他顶点的最短路径，可以通过经典的Dijkstra（狄杰斯特拉）算法求解；二是求每对顶点间的最短路径，可通过Floyd（佛洛依德）算法求解。

Dijkstra和Floyd还有一个很大的区别就是Dijkstra不能求解权值为负的问题，Floyd可以求解。

这里先简单介绍下Dijkstra算法思想。

我们计算从顶点1到其他顶点的最短距离。

开始会选择从以1开始的边中最短的，也就是1->5，到了5发现有5->2,5->3,5->4可以选，我们该选哪个呢，肯定会选5->4,因为权值最小，到了4又有4->1,4->3可以选因为前面我们1是顶点了，已经取过了，就不能再取了，那只能选4->3了，可是我们真的能选吗？现在1->5->4->3的权值为5+2+6 = 13可是1->5->2->3的权值只有5+3+1 = 9这不是更短吗？

所以这就需要我们时时维护更新到达该点的路径，发现更短的就更新。

我们每轮确定一个顶点的最短路径。

下面我们先采用临接矩阵来实现。

邻接矩阵graph为：

我们还需要用一个一维数组 dis 来存储 1 号顶点到其余各个顶点的初始路程，如下。

我们将此时 dis 数组中的值称为最短路的“估计值”。

既然是求 1 号顶点到其余各个顶点的最短路程，那就先找一个离 1 号顶点最近的顶点。通过数组 dis 可知当前离 1 号顶点最近是 2 号顶点。当选择了 2 号顶点后，dis[2]的值就已经从“估计值”变为了“确定值”，即 1 号顶点到 2 号顶点的最短路程就是当前 dis[2]值。为什么呢？你想啊，目前离 1 号顶点最近的是 2 号顶点，并且这个图所有的边都是正数，那么肯定不可能通过第三个顶点中转，使得 1 号顶点到 2 号顶点的路程进一步缩短了。

1
2
3
4
5
6
7
8
9
10
11
//找到离 1 号顶点最近的顶点
int minDis = inf;
for(int j = 1; j <= n; j++){
    //没有访问过并且距离小于当前距离，更新
    if(visited[j] == 0 && dis[j] < minDis){
        minDis = dis[j];
        u = j;
    }
}
//标记已经访问过
visited[u] = 1;

既然选了 2 号顶点，接下来再来看 2 号顶点有哪些出边呢。有 2->3 和 2->4这两条边。先讨论通过 2->3 这条边能否让 1 号顶点到 3 号顶点的路程变短。也就是说现在来比较 dis[3]和 dis[2]+graph[2][3]的大小。其中 dis[3]表示 1 号顶点到 3 号顶点的路程。dis[2]+graph[2][3]中 dis[2]表示 1 号顶点到 2 号顶点的路程，graph[2][3]表示 2->3 这条边。所以 dis[2]+graph[2][3]就表示从 1 号顶点先到 2 号顶点，再通过 2->3 这条边，到达 3 号顶点的路程。

我们发现 dis[3]=12，dis[2]+graph[2][3]=1+9=10，dis[3] > dis[2]+graph[2][3]，因此 dis[3]要更新为 10。这个过程有个专业术语叫做“松弛”。即 1号顶点到 3号顶点的路程即 dis[3]，通过2->3 这条边松弛成功。这便是 Dijkstra 算法的主要思想：通过“边”来松弛 1号顶点到其余各个顶点的路程。

1
2
3
4
5
6
7
8
for(int v = 1; v <= n; v++){
    if(graph[u][v] < inf){
        //dis[v]表示原来到顶点 v 的距离，dis[u] + graph[u][v]是从新顶点到 v 的距离
        if(dis[v] > dis[u] + graph[u][v]){
            dis[v] = dis[u] + graph[u][v];
        }
    }
}

下面同理：

刚才我们对 2 号顶点所有的出边进行了松弛。松弛完毕之后 dis 数组为：

同理：

最终的dis为

OK，现在来总结一下刚才的算法。算法的基本思想是：每次找到离源点（上面例子的源点就是 1 号顶点）最近的一个顶点，然后以该顶点为中心进行扩展，最终得到源点到其余所有点的最短路径。基本步骤如下：

  • 将所有的顶点分为两部分：已知最短路程的顶点集合 P 和未知最短路径的顶点集合 Q。最开始，已知最短路径的顶点集合 P 中只有源点一个顶点。我们这里用一个visited[i]数组来记录哪些点在集合 P 中。例如对于某个顶点 i，如果 visited[i]为 1 则表示这个顶点在集合 P 中，如果 visited[i]为 0 则表示这个顶点在集合 Q 中。
  • 设置源点 s 到自己的最短路径为 0 即 dis=0。若存在源点有能直接到达的顶点 i，则把 dis[i]设为 graph[s][i]。同时把所有其它（源点不能直接到达的）顶点的最短路径为设为 ∞。
  • 在集合 Q 的所有顶点中选择一个离源点 s最近的顶点 u（即 dis[u]最小）加入到集合 P。并考察所有以点 u 为起点的边，对每一条边进行松弛操作。例如存在一条从 u 到 v 的边，那么可以通过将边 u->v 添加到尾部来拓展一条从 s 到 v 的路径，这条路径的长度是 dis[u]+graph[u][v]。如果这个值比目前已知的 dis[v]的值要小，我们可以用新值来替代当前dis[v]中的值。
  • 重复第 3 步，如果集合 Q 为空，算法结束。最终 dis数组中的值就是源点到所有顶点的最短路径。

完整代码如下：

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
82
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

int graph[10][10];
int dis[10];
int visited[10];
int n,m;    // n 表示顶点个数，m表示边数
const int inf = INT_MAX / 2;

void init(){
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(i == j) graph[i][j] = 0;
            else graph[i][j] = inf;
        }
    }
}
//构建边
void add(int from, int to, int weight){
    graph[from][to] = weight;
}

void dijkstra(int u){
    for(int i = 1; i <= n - 1; i++){
        //找到离 1 号顶点最近的顶点
        int minDis = inf;
        for(int j = 1; j <= n; j++){
            //没有访问过并且距离小于当前距离，更新
            if(visited[j] == 0 && dis[j] < minDis){
                minDis = dis[j];
                u = j;
            }
        }
        //标记已经访问过
        visited[u] = 1;

        for(int v = 1; v <= n; v++){
            if(graph[u][v] < inf){
                //dis[v]表示原来到顶点 v 的距离，dis[u] + graph[u][v]是从新顶点到 v 的距离
                if(dis[v] > dis[u] + graph[u][v]){
                    dis[v] = dis[u] + graph[u][v];
                }
            }
        }
    }
}

int main(){
    cin >> n >> m;
    //初始化
    init();
    //读入边
    for(int i = 1; i <= m; i++){
        int from, to, weight;
        cin >> from >> to >> weight;
        add(from, to, weight);
    }
    //初始化 dis 数组，这里是 1 号顶点到其余各个顶点的初始路程
    for(int i = 1; i <= n; i++){
        dis[i] = graph[1][i];
    }
    //初始化visited数组,标记有没有访问过
    for(int i = 1; i<= n; i++){
        visited[i] = 0;
    }
    //1号节点访问过
    visited[1] = 1;
    //dijskra算法
    dijkstra(1);
    //输出最后结果
    for(int i = 1; i <= n; i++){
        if(i == n) cout << dis[i] << endl;
        else cout << dis[i] << " ";
    }
    return 0;
}

输入：

6 9

1 2 1

1 3 12

2 3 9

2 4 3

3 5 5

4 3 4

4 5 13

4 6 15

5 6 4

输出：

0 1 8 4 13 17

743. 网络延迟时间

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

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

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

###示例 1：

输入：times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2

输出：2

思想：

方法一：Dijkstra邻接矩阵

负责度为O(N^2)

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
class Solution {
public:
    const int inf = INT_MAX / 2;
    vector<vector<int> > graph;
    vector<int> dis;
    vector<int> visited;
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        graph.resize(n + 1, vector<int>(n + 1, 0));
        dis.resize(n + 1, 0);
        visited.resize(n + 1, 0);
        //初始化 graph
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                if(i == j) graph[i][j] = 0;
                else graph[i][j] = inf;
            }
        }
        for(vector<int> tmp : times){
            int from = tmp[0];
            int to = tmp[1];
            int weight = tmp[2];
            graph[from][to] = weight;
        }
        //初始化dis
        for(int i = 1; i <= n; i++){
            dis[i] = graph[k][i];
        }
        visited[k] = 1;
        dijkstra(k, n);
        int res = 0;
        for(int i = 1; i <= n; i++){
            if(dis[i] >= inf) return -1;
            else res = max(dis[i], res);
        }
        return res;
    }
    void dijkstra(int u, int n){
        for(int i = 1; i <= n - 1; i++){
            int minDis = inf;
            for(int j = 1; j <= n; j++){
                if(visited[j] == 0 && dis[j] < minDis){
                    minDis = dis[j];
                    u = j;
                }
            }
            visited[u] = 1;
            for(int v = 1; v <= n; v++){
                if(graph[u][v] < inf){
                    if(dis[v] > dis[u] + graph[u][v]){
                        dis[v] = dis[u] + graph[u][v];
                    }
                }
            }
        }
    }
};
方法二： 邻接矩阵+小根堆

复杂度为O(N^2)

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
class Solution {
public:
    const int inf = INT_MAX / 2;
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        vector<vector<pair<int, int> > > edge(n + 1);
        for(vector<int> tmp : times){
            //构建邻接表
            edge[tmp[0]].push_back(make_pair(tmp[1], tmp[2]));
        }
        //以节点 k 为起点到其他节点的最短路径
        vector<int> dist(n + 1, inf);
        //k 到 k 的最短距离为 0 
        dist[k] = 0;
        //小根堆greater<>,大根堆less<>
        priority_queue<pair<int,int>, vector<pair<int, int> >, greater<>>q;
        //从起点开始BFS
        q.emplace(0, k);
        while(! q.empty()){
            // pair<int,int> p = q.top();
            auto p = q.top();
            q.pop();
            int curDistFromStart = p.first;
            int curNodeID = p.second;
          	//小于就跳过
            if(dist[curNodeID] < curDistFromStart){
                continue;
            }
            //将 x 的相邻节点装入队列
            for(auto &neighbor : edge[curNodeID]){
                int nextNodeID = neighbor.first;
                int distToNextNode = dist[curNodeID] + neighbor.second;
                //更新,距离小于原来节点到当前节点的距离
                if(distToNextNode < dist[nextNodeID]){
                    dist[nextNodeID] = distToNextNode;
                    q.emplace(distToNextNode, nextNodeID);
                }
            }
        }
        int res = 0;
        for(int i = 1; i <= n; i++){
            if(dist[i] >= inf) return -1;
            else res = max(res, dist[i]);
        }
        return res;
    }
};
方法三：floyd

floyd

时间复杂度：O(n^3)

空间复杂度：O(n^2)

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
class Solution {
public:
    vector<vector<int> > graph;
    const int inf = INT_MAX / 2;
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        graph.resize(n + 1, vector<int>(n + 1, 0));
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                if(i == j) graph[i][j] = 0;
                else graph[i][j] = inf;
            }
        }
        //存图
        for(vector<int> tmp : times){
            int from = tmp[0];
            int to = tmp[1];
            int weight = tmp[2];
            graph[from][to] = weight;
        }
        //最短路
        floyd(n);
        int res = 0;
        for(int i = 1; i <= n; i++){
            if(graph[k][i] >= inf) return -1;
            else res = max(res, graph[k][i]);
        }
        return res;
    }
    void floyd(int n){
        //floyd基本流程三层循环
        //枚举中转点 - 枚举起点 - 枚举终点 - 松弛操作
        for(int p = 1; p <= n; p++){
            for(int i = 1; i <= n; i++){
                for(int j = 1; j <= n; j++){
                    graph[i][j] = min(graph[i][j], graph[i][p] + graph[p][j]);
                }
            }
        }
    }
};