3. 最短路径

3.1. Bellman-Ford 算法

时间复杂度 \(\mathcal{O}(VE)\) ，其中顶点数 \(V\) ，边数 \(E\) 。如果不存在负圈（一条回路的代价和为负），那么每一条最短路径都不会经过同一个顶点两次，因此 while 循环最多执行 \(V-1\) 次。

 1struct edge {int from, to, cost;};
 2
 3edge es[MAX_E];
 4
 5int d[MAX_V]; // 最短距离
 6int V, E; // 顶点数，边数
 7
 8// 从顶点 s 出发的最短距离（假设不存在负圈）
 9void shortestPath(int s)
10{
11  fill(d, d+V, INF);
12  d[s] = 0;
13  while(true)
14  {
15    bool update = false;
16    for(int i = 0; i < E; ++i)
17    {
18      edge e = es[i];
19      if(d[e.from] != INF && d[e.to] > d[e.from] + e.cost)
20      {
21        d[e.to] = d[e.from] + e.cost;
22        update = true;
23      }
24    }
25    if(!update) break;
26  }
27}

检查负圈：如果第 \(V\) 次循环还有更新，则表明存在负圈，返回 true。

 1bool findNegativeLoop()
 2{
 3  fill(d, d+V, 0); // 初始化为 0，防止因为是 d[e.from] == INF 而停止更新
 4  for(int i = 0; i < V; ++i)
 5  {
 6    for(int j = 0; j < E; ++j)
 7    {
 8      edge e = es[j];
 9      if(d[e.to] > d[e.from] + e.cost)
10      {
11        d[e.to] = d[e.from] + e.cost;
12        if(i == V-1) return true;
13      }
14    }
15  }
16  return false;
17}

3.2. Dijkstra 算法

适合处理没有负边的情形。每一次循环，在尚未确定最短距离的顶点中，d[i] 最小的顶点就是下一个确定的顶点。但是如果存在负边，d[i] 在之后的更新中还会变小，因此算法失效。

  • 方法一

    直接使用邻接矩阵，时间复杂度 \(\mathcal{O}(V^2)\) 。

 1int cost[MAX_V][MAX_V];
 2int d[MAX_V];
 3bool used[MAX_V];
 4int V;
 5
 6void dijkstra(int s)
 7{
 8  fill(d, d+V, INF);
 9  d[s] = 0;
10  fill(used, used+V, false);
11
12  while(true)
13  {
14    int v = -1;
15    for(int u = 0; u < V; ++u)
16    {
17      if(!used[u] && (v == -1 || d[u] < d[v])) v = u;
18    }
19
20    if(v == -1 || d[v] == INF) break;
21    // v == -1 表示所有顶点都找到了最短距离
22    // d[v] == INF 表示后面所有的顶点都已经不可达，直接结束循环
23
24    used[v] = true;
25    for(int u = 0; u < V; ++u)
26    {
27      d[u] = min(d[u], d[v] + cost[v][u]);
28    }
29  }
30}
  • 方法二

    使用最小堆（优先队列），堆中元素个数为 \(\mathcal{O}(V)\)，出队（弹出最小值）的次数为 \(\mathcal{O}(E)\)，时间复杂度 \(\mathcal{O}(E \log V)\)。

 1struct edge {int to, cost;};
 2typedef pair<int, int> P; // first：最短距离，second：顶点
 3
 4int V;
 5vector<edge> G[MAX_V]; // 边
 6int d[MAX_V];
 7
 8void dijkstra(int s)
 9{
10  priority_queue<P, vector<P>, greater<P>> que;
11
12  fill(d, d+V, INF);
13  d[s] = 0;
14
15  que.push(P(0, s));
16  while(!que.empty())
17  {
18    P p = que.top();
19    que.pop();
20
21    int v = p.second;
22    if(d[v] < p.first) continue;
23
24    for(int i = 0; i < G[v].size(); ++i)
25    {
26      edge e = G[v][i];
27      if(d[e.to] > d[v] + e.cost)
28      {
29        d[e.to] = d[v] + e.cost;
30        que.push(P(d[e.to], e.to));
31      }
32    }
33  }
34}

3.3. 实例

  • [LeetCode] Shortest Path to Get All Keys 获取所有钥匙的最短路径。Hint：需要一个状态量来表示到达当前位置已经获得的钥匙（BitMap）；当且仅当钥匙状态不相同时，才可以重复经过某一个坐标点。

    https://leetcode.com/problems/shortest-path-to-get-all-keys/

    \(\color{darkgreen}{Code}\)

     1class Solution
 2{
 3public:
 4    int shortestPathAllKeys(vector<string>& grid)
 5    {
 6        if(grid.empty() || grid[0].empty()) return 0;
 7        int row = grid.size();
 8        int col = grid[0].size();
 9        vector<vector<vector<bool>>> visited(row, vector<vector<bool>>(col, vector<bool>(64, false))); // bitmap, row x col x 2^6
10        queue<pair<int,int>> que; // 坐标和key
11        int nkey = 0;
12        for(int i = 0; i < row; ++i)
13        {
14            for(int j = 0; j < col; ++j)
15            {
16                if(grid[i][j] == '@')
17                {
18                    que.push({i*col+j,0});
19                    visited[i][j][0] = true;
20                }
21                if('a' <= grid[i][j] && grid[i][j] <= 'f') nkey |= 1 << (grid[i][j] - 'a');
22            }
23        }
24        int step = 0;
25        while(!que.empty())
26        {
27            int qsize = que.size();
28            for(int i = 0; i < qsize; ++i) // 从各个出发点出发，同步向前走一步
29            {
30                auto p = que.front();
31                que.pop();
32                int x = p.first/col, y = p.first%col;
33                int carry = p.second;
34                if(carry == nkey) return step;
35                for(int j = 0; j < 4; ++j)
36                {
37                    int nx = x + mv[j][0];
38                    int ny = y + mv[j][1];
39                    int nk = carry;
40                    if(nx < 0 || nx >= row || ny < 0 || ny >= col) continue;
41                    if(grid[nx][ny] == '#') continue;
42                    if('A' <= grid[nx][ny] && grid[nx][ny] <= 'F')
43                    {
44                        if(!(nk & (1 << (grid[nx][ny] - 'A')))) continue;
45                        // nk &= ~ (1 << (grid[nx][ny] - 'A')); // 开门不会消耗钥匙
46                    }
47                    if('a' <= grid[nx][ny] && grid[nx][ny] <= 'f') nk |= 1 << (grid[nx][ny] - 'a');
48                    if(!visited[nx][ny][nk]) // 当前钥匙状态为 nk , 未访问过 (nx, ny)
49                    {
50                        visited[nx][ny][nk] = true;
51                        que.push({nx*col+ny, nk});
52                    }
53                }
54            }
55            ++step; // 此时队列中保存的是从各个出发点出发，走完 step 步的结果
56        }
57        return -1;
58    }
59private:
60    static const int mv[4][2];
61};
62const int Solution::mv[4][2] = {{-1,0},{0,-1},{0,1},{1,0}};

  • [LeetCode] 到达目的地的方案数。

    https://leetcode.cn/problems/number-of-ways-to-arrive-at-destination

    \(\color{darkgreen}{Code}\)

     1from queue import PriorityQueue
 2
 3INF = float('inf')
 4MOD = 10 ** 9 + 7
 5
 6class Solution:
 7    def countPaths(self, n: int, roads: List[List[int]]) -> int:
 8        adj = [[] for _ in range(n)] ## 邻接表
 9        for u, v, time in roads:
10            adj[u].append((v, time))
11            adj[v].append((u, time))
12        d = [0] + [INF] * (n - 1) ## 最短距离
13        pn = [1] + [0] * (n - 1) ## 最短路径数量
14        pq = PriorityQueue()
15        pq.put((0, 0)) ## (从起点到某顶点的距离，顶点)
16        while not pq.empty():
17            t, u = pq.get()
18            if d[u] < t:
19                continue
20            for v, time in adj[u]:
21                if d[v] == d[u] + time:
22                    pn[v] += pn[u]
23                elif d[v] > d[u] + time:
24                    d[v] = d[u] + time
25                    pn[v] = pn[u]
26                    pq.put((d[u] + time, v)) ## 发现更短的路径才放入队列
27                pn[v] = pn[v] % MOD
28        return pn[-1]

  • [LeetCode] 到达目的地的最短时间。

    https://leetcode.com/problems/minimum-time-to-visit-a-cell-in-a-grid

    \(\color{darkgreen}{Code}\)

     1from queue import PriorityQueue
 2class Solution:
 3    def minimumTime(self, grid: List[List[int]]) -> int:
 4        m, n = len(grid), len(grid[0])
 5        assert m >= 2 and n >= 2
 6        ## 先排除一步也走不出去的情形
 7        if grid[0][1] > 1 and grid[1][0] > 1:
 8            return -1
 9        visited = [[False] * n for _ in range(m)]
10        pq = PriorityQueue()
11        pq.put((0, 0, 0)) ## (time, row, col)
12        visited[0][0] = True
13        while not pq.empty():
14            t, r, c = pq.get()
15            if r == m - 1 and c == n - 1:
16                return t
17            for dr, dc in [(-1,0), (0,-1), (1,0), (0,1)]:
18                _r, _c = r + dr, c + dc
19                if 0 <= _r < m and 0 <= _c < n and not visited[_r][_c]:
20                    visited[_r][_c] = True
21                    if grid[_r][_c] <= t + 1:
22                        ## 下一步直接迈进 (_r, _c)
23                        pq.put((t + 1, _r, _c))
24                    else:
25                        ## 在第 t 和 t-1 步之间来回踱步，以达到时间要求
26                        ## 这里导致先入队的不一定是先到达的节点，所以使用的是优先队列
27                        diff = grid[_r][_c] - t
28                        if diff & 1:
29                            pq.put((grid[_r][_c], _r, _c))
30                        else:
31                            pq.put((grid[_r][_c] + 1, _r, _c))
32        return -1