算法

最短路径问题

Posted by Meng Cao on 2019-07-07

故事不长。

图论中的最短路径问题，通常可以用dijkstra算法，bellman-ford算法和Floyd-Warshall算法。

Dijkstra算法使用广度优先搜索，解决赋权有向图的单元最短路径问题。具体而言，固定一个节点作为源节点，找到该节点到其他节点的最短路径，生成一颗最短路径树。

Dijkstra算法

算法描述

算法维护两个顶点集合 S 和 Q。集合 S 保留所有已知最小 d[v] 值的顶点 v ，而集合 Q 则保留其他所有顶点。集合S初始状态为空，而后每一步都有一个顶点从 Q 移动到 S。这个被选择的顶点是 Q 中拥有最小的 d[u] 值的顶点。当一个顶点 u 从 Q 中转移到了 S 中，算法对 u 的每条外接边 (u, v) 进行拓展。
注：d[u] 表示源节点到节点u之间的最短路径距离。

伪代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 1  function Dijkstra(G, w, s)
 2     for each vertex v in V[G]        // 初始化
 3           d[v] := infinity           // 将各点的已知最短距离先设成无穷大
 4           previous[v] := undefined   // 各点的已知最短路径上的前趋都未知
 5     d[s] := 0                        // 因为出发点到出发点间不需移动任何距离，所以可以直接将s到s的最小距离设为0
 6     S := empty set
 7     Q := set of all vertices
 8     while Q is not an empty set      // Dijkstra算法主体
 9           u := Extract_Min(Q)
10           S.append(u)
11           for each edge outgoing from u as (u,v)
12                  if d[v] > d[u] + w(u,v)             // 拓展边（u,v）。w(u,v)为从u到v的路径长度。
13                        d[v] := d[u] + w(u,v)         // 更新路径长度到更小的那个和值。
14                        previous[v] := u              // 纪录前趋顶点

如果我们只对在 s 和 t 之间查找一条最短路径的话，我们可以在第9行添加条件如果满足 u = t 的话终止程序。

可以使用priority_queue来优化上述程序，伪代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
1  function Dijkstra(Graph, source):
2      dist[source] ← 0                           // Initialization
3
4      create vertex set Q
5
6      for each vertex v in Graph:           
7          if v ≠ source
8              dist[v] ← INFINITY                 // Unknown distance from source to v
9          prev[v] ← UNDEFINED                    // Predecessor of v
10
11         Q.add_with_priority(v, dist[v])
12
13
14     while Q is not empty:                      // The main loop
15         u ← Q.extract_min()                    // Remove and return best vertex
16         for each neighbor v of u:              // only v that are still in Q
17             alt ← dist[u] + length(u, v) 
18             if alt < dist[v]
19                 dist[v] ← alt
20                 prev[v] ← u
21                 Q.decrease_priority(v, alt)
22
23     return dist, prev

时间复杂度

第一层循环（第14行）：O(V)

取出Q中最小的元素（第15行）：若不用堆则 O(V)；若用堆则 O(log V)

第二层循环（第16行）：O(E / V)

更新V的当下最短路径：若不用堆则 O(1)；若用堆则 O(log V)

综上:

若用堆，O(V * (log V +E / V log V)) = O(V log V + E log V) -> O(E log V)
若不用堆，O(V * (V +E / V * 1)) = O(V^2 + E) -> O(V^2)

Bellman-ford算法

算法描述

它的原理是对图进行|V|-1次松弛操作，得到所有可能的最短路径。
Dijkstra算法以贪心法选取未被处理的具有最小权值的节点，然后对其的出边进行松弛操作；而Bellman-ford算法简单地对所有边进行松弛操作，共|V|-1次，其中|V|是图的点的数量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
procedure BellmanFord(list vertices, list edges, vertex source)
   // 读入边和节点的列表，并对distance和predecessor写入最短路径

   // 初始化图
   for each vertex v in vertices:
       if v is source then distance[v] := 0 // source节点距离为0
       else distance[v] := infinity // 其他设置为Inf
       predecessor[v] := null

   // 对每一条边重复操作
   for i from 1 to size(vertices)-1:
       for each edge (u, v) with weight w in edges:
           if distance[u] + w < distance[v]:
               distance[v] := distance[u] + w
               predecessor[v] := u

   // 检查是否有负权重的环
   //for each edge (u, v) with weight w in edges:
   //    if distance[u] + w < distance[v]:
   //        error "含有包含负权重的环"

每次松弛操作实际上是对相邻节点的访问，第n次松弛操作保证了所有深度为n的路径最短。由于图的最短路径最长不会经过超过|V|-1条边，所以可知贝尔曼-福特算法所得为最短路径。

时间复杂度

O(V*E)

Floyd-Warshall算法

算法描述

解决图中任意两点之间最短路径的问题。本质上是一个动态规划问题：
D[i][j][k]表示从i到j，使用前k个顶点([1,k])作为中间节点的最短路径长度。

  1. 若最短路径经过点k, 则D[i][j][k] = D[i][k][k-1] + D[k][j][k-1]
  2. 若最短路径不经过点k, 则D[i][j][k] = D[i][j][k-1]
    所以 D[i][j][k] = min(D[i][j][k-1], D[i][k][k-1]+D[k][j][k-1])
1
2
3
4
5
6
7
8
9
10
11
1 let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
2 for each vertex v
3    dist[v][v] ← 0
4 for each edge (u,v)
5    dist[u][v] ← w(u,v)  // the weight of the edge (u,v)
6 for k from 1 to |V|
7    for i from 1 to |V|
8       for j from 1 to |V|
9          if dist[i][j] > dist[i][k] + dist[k][j] 
10             dist[i][j] ← dist[i][k] + dist[k][j]
11         end if

时间复杂度

时间复杂度O(n^3), 空间复杂度O(n^2)

例题

743.Network Delay Time

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
class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int N, int K) {
        vector<vector<pair<int,int>>> graph(N+1);
        //(u,v,w)
        for(const auto& t : times)
            graph[t[0]].emplace_back(t[1],t[2]);
        const int inf = 1e9;
        vector<int> dist(N+1, inf);
        dist[K] = 0;
        //(dist[i], i)
        priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
        pq.emplace(0, K);
        vector<int> visited(N+1, 0);
        
        while(!pq.empty()) {
            auto p = pq.top(); pq.pop();
            int u = p.second;
            if(visited[u]) continue;
            visited[u] = 1;
            for(auto& to : graph[u]) {
                int v = to.first;
                int w = to.second;
                if(dist[v] > dist[u] + w) {
                    dist[v] = dist[u] + w;
                    pq.emplace(dist[v], v);
                }
            }
        }
        int ans = *max_element(dist.begin()+1, dist.end());
        return ans == inf ? -1 : ans;
    }
};

bellman-ford算法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int N, int K) {
        constexpr int MAX_TIME = 1e9;
        vector<int> dist(N, MAX_TIME);
        dist[K-1] = 0;
        for(int i=1; i<N; ++i)
            for(const auto& time : times) {
                int u = time[0] - 1;
                int v = time[1] - 1;
                int w = time[2];
                dist[v] = min(dist[v], dist[u] + w);
            }
        int max_dist = *max_element(dist.begin(), dist.end());
        return max_dist==MAX_TIME ? -1 : max_dist;
    }
};

Floyd-Warshall算法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int N, int K) {
        constexpr int MAX_TIME = 1e9;
        vector<vector<int>> d(N, vector<int>(N, MAX_TIME));
        
        for(auto time : times)
            d[time[0]-1][time[1]-1] = time[2];
        
        for(int i=0; i<N; ++i)
            d[i][i] = 0;
        
        for(int k=0; k<N; ++k)
            for(int i=0; i<N; ++i)
                for(int j=0; j<N; ++j)
                    d[i][j] = min(d[i][j], d[i][k]+d[k][j]);
        
        int ans = *max_element(d[K-1].begin(), d[K-1].end());
        
        return ans>= MAX_TIME ? -1 : ans;
    }
};

787 Cheapest Flights Within K Stops

dp[k][i]: min cost from src to i taken up to k flights (k-1 stops) //乘坐k次航班，从src到i的最小花费

init: dp[0:k+2][src] = 0 //初始化

transition: dp[k][i] = min(dp[k-1][j] + price[j][i])
dp[k][v] = min(dp[k-1][u] + cost[u][v], dp[k-1][v])

ans: dp[K+1][dst]
Time complexity: O(k * |flights|) / O(k*n^2)

Space complexity: O(k*n) -> O(n)

w/o space compression O(k*n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
        constexpr int KInfCost = 1e9;
        vector<vector<int>> dp(K+2, vector<int>(n, KInfCost));
        
        dp[0][src] = 0;
        
        for(int i=1; i<=K+1; ++i) {
            dp[i][src] = 0;
            for(const auto& p : flights)
                dp[i][p[1]] = min(dp[i][p[1]], dp[i-1][p[0]]+p[2]);
        }
        
        return dp[K+1][dst] >= KInfCost ? -1 : dp[K+1][dst];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// with space compression
class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
        constexpr int KInfCost = 1e9;
        vector<int> cost(n, KInfCost);
        cost[src] = 0;
        
        for(int i=0; i<=K; ++i) {
            vector<int> tmp(cost);//每次构建一个滚动数组，表示下一阶段的结果
            for(const auto& p : flights)
                tmp[p[1]] = min(tmp[p[1]], cost[p[0]]+p[2]);
            cost.swap(tmp);
        }
        return cost[dst]>=KInfCost ? -1 : cost[dst];
    }
};

882 Reachable Nodes In Subdivided Graph

FEATURED TAGS
算法
FRIENDS