【图算法】Dijkstra——最短路径

发表于 更新于 分类于 阅读次数：
本文字数： 3.7k 阅读时长 ≈ 3 分钟

Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。算法要求所有边的权重必须是非负的。

问题：
给定三个集合V、 E、 W，其中，V存放着所有顶点的index/name（下面代码里的V为节点数），E存放所有边的信息，W存放着E中对应边的权重（下面代码里把E和W合并到在一起了）。现在给出V中的一个顶点A，求从A出发到其他顶点的最短路径，即经过边的权重和最小。

基本思路：

  1. 建立优先队列pq（小顶堆），队列里存储在当前条件下（表示以后可能还会被更新）离源点最近距离的节点及其距离(距离是为了供优先队列比较大小用)，初始只有源点，其距离值为0；还需要一个dist数组以及visited数组，数组长度均为节点个数；dist用来记录当前状态下各个节点离源点的最短路径，初始除源点外的值为无穷大，源点的值为0；visited用来记录各个节点是否已经被优先队列弹出过，若为True则表示当前节点被弹出过。
  2. 如果优先队列不为空，则弹出优先队列队顶元素，即下一个已经更新过最短路径的节点，如果该节点已经被访问了，即表示在弹出该节点之前该节点有一个比当前最短路径更近的情况被弹出过，则此情况应该丢弃。这也说明我们每次加入优先队列的元素不一定就是最短路径的情况，但是优先队列优先弹出最短路径，这也是为什么我们用优先队列而不是普通队列的原因。
  3. 如果弹出的节点之前没有被访问过/弹出过，那么该节点的最短路径就被确定了，然后遍历与该节点直接相连的节点，并更新这些节点的最短路径。
  4. 如果优先队列为空，则说明所有节点的最短路径都已经被确定了，结束循环。

原始思路1:

  1. 遍历V - S中的所有点，求出从初始点A只经过S中顶点到达该点的路径权重和dist，若不存在路径，则dist设置为$\infty$；
  2. 找出第一步中的最小的dist，将该dist对应的顶点放入S中，该dist值放入U中；
  3. 重复1、2直到V等于S为止。

原始思路2：

  1. 遍历S中的点，找出所有E中从该点出发但是终点不在S中的边，算出对应的dist；
  2. 找出第一步中的最小dist，将该dist对应的顶点放入S中，该dist值放入U中；
  3. 重复1、2直到V等于S为止。

Python 参考源码:

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
import sys
import heapq
MAX_INT = sys.maxsize

def add_edges(adj, u, v, w):
    """build graph by adding edges"""
    adj[u].append((v, w));
    adj[v].append((u, w));

def dijkstra(adj, V, src):
    # 用优先队列(默认小顶堆)完成最小dist节点的动态选取
    pq = []
    # dist表示src到每个顶点的最短路径，初始为MAX_INT
    dist = [MAX_INT]*V
    # visited记录节点是否被当作最小dist节点访问过
    visited = [False]*V

    # 优先队列初始只有起始点，起始点的dist为0
    heapq.heappush(pq, (0, src))
    dist[src] = 0

    while pq:
        # 弹出当前距离源点dist最小而且未被访问的节点
        wt, u = heapq.heappop(pq)
        if visited[u]:
            continue
        visited[u] = True
        # 遍历该节点直接相连的节点并更新对应节点的dist
        for v, w in adj[u]:
            if dist[v] > dist[u] + w:
                dist[v] = dist[u] + w
                heapq.heappush(pq, (dist[v], v))

    # 打印结果
    for i, d in enumerate(dist):
        print(f'{i}: {d}')

if __name__ == '__main__':
    # 图中顶点的个数
    V = 9
    # 图中边及其权重的信息
    EW = [(0, 1, 4), (0, 7, 8), (1, 2, 8), (1, 7, 11), (2, 3, 7), (2, 8, 2), (2, 5, 4),
          (3, 4, 9), (3, 5, 14), (4, 5, 10), (5, 6, 2), (6, 7, 1), (6, 8, 6), (7, 8, 7)]
    adj = [[] for _ in range(V)]

    # 构建无向图
    for ew in EW:
        add_edges(adj, ew[0], ew[1], ew[2])

    # 执行Dijkstra算法
    dijkstra(adj, V, 0)

C++：

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
#include <iostream>
#include <vector>
#include <queue>
#include <utility>

using namespace std;
# define INF 0x3f3f3f3f

// pair定义在utility头文件里，这里用类型别名简化代码
typedef pair<int, int> iPair;

void addEdge(vector<vector<iPair>> &adj, int u, int v, int wt) {
    adj[u].push_back(make_pair(v, wt));
    adj[v].push_back(make_pair(u, wt));
}

void dijkstra(vector<vector<iPair>> &adj, int V, int src) {
    priority_queue<iPair, vector<iPair>, greater<iPair>> pq;
    
    vector<int> dist(V, INF);
    vector<bool> visited(V, false);
    
    pq.push(make_pair(0, src));
    dist[src] = 0;
    
    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        if (visited[u]) {
            continue;
        }
        visited[u] = true;
        // [v, weight]这个用法在C++17以后才有，C++11要用下面注释掉的版本
        for (const auto &[v, weight]: adj[u]) {
        //for (const auto &x: adj[u]) {
            //int v = x.first;
            //int weight = x.second;
            
            if (dist[v] > dist[u] + weight) {
                dist[v] = dist[u] + weight;
                pq.push(make_pair(dist[v], v));
            }
        }
    }
    cout << "Vetex Distance from Source" << endl;
    for (int i = 0; i < V; i++) {
        cout << i << "\t\t" << dist[i] << endl;
    }
}

int main(int argc, const char * argv[]) {
    int V = 9;
    vector<vector<iPair>> adj(V);
    vector<vector<int>> edges = {
        {0, 1, 4}, {0, 7, 8}, {1, 2, 8}, {1, 7, 11}, {2, 3, 7}, {2, 8, 2}, {2, 5, 4},
        {3, 4, 9}, {3, 5, 14}, {4, 5, 10}, {5, 6, 2}, {6, 7, 1}, {6, 8, 6}, {7, 8, 7}
    };
    // 用引用是为了避免不必要的拷贝操作
    for (const auto &i: edges) {
        addEdge(adj, i[0], i[1], i[2]);
    }
    
    dijkstra(adj, V, 0);
    return 0;
}