单源最短路

Dijkstra 算法

在图中，如果确定了起点，那么对于点P而言，假设其与起点有路径L1，由起点前往其最短的路径必然为L1或与起点最短路小于L1的点组成的路径，不可能由更长的路径回头组成。

也就是说，只要我每次都选取未确定最短路节点中，距离起点最近的一条，那么就可以肯定，这一定是前往这个节点的最短路：因为前往这个节点的路不可能由其他更长的未确定节点推出。

选定第一个节点之后，通过第一个节点将邻居节点的位置更新，把其涉及的位置可能性全部更新入距离数组中，就不需要再考虑这个节点了。

此时我们会发现，在当前考虑的最短距离下，前往最短距离的那个点有且仅有目前已确定的点推导出的最短路，而无法从其他更长的路回头再前往那个点，算法正确性成立。

那么现在你可能有疑惑：“我知道当前最小的一定是最短路，但如果真正的最短路藏在后面还没被更新到怎么办？”

其实只需要保证，一开始的最短路是正确的，那么后续加入最短路时，类似于带权的BFS算法，当前最小的路一定是真正的最短路

模板题

week14-1 单源最短路
题目描述

给定一个n个节点m条边的带权有向图G，节点编号从1到n，保证图中没有重边和自环。

现在，你要求这个图中节点1到所有n个节点的最短路径的权值。

输入描述

第1行包含两个整数n,m (2≤n≤1e3,1≤m≤1e5)，表示节点个数和边数。
接下来m行，每行包含三个整数u,v,w (1≤u,v≤n,1≤w≤1e9)，表示从节点u和节点v有一条权值为w的有向边。

输出描述

输出一行，包含n个整数，第i个整数表示节点1到节点i的最短路径的权值，如果不存在这样的路径，输出−1代替

输入样例1

1
2
3
4
5
6
7
8
9
10
11
12
7 11
5 2 6
3 4 1
3 5 4
5 4 8
1 3 7
4 1 5
3 7 9
4 5 2
1 5 7
6 7 6
1 2 1

输出样例1

0 1 7 8 7 -1 16

代码：

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
#include<vector>
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
#define int long long
struct edge{
    int to;
    int len;
};
vector<edge> a[1005];
int dist[1005];
int visited[1005]; 
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
int n,m;
signed main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        a[u].push_back({v,w});
    }
    for(int i=1;i<=n;i++){
        dist[i] = 1e16;
    }
    dist[1]=0;
    pq.push({0,1});
    while(pq.size()!=0){
        int w = pq.top().first,v = pq.top().second;
        pq.pop();
        if(visited[v]) continue;
        visited[v] = true;
        dist[v] = w;
        for(auto& e:a[v]){
            int to = e.to;
            int len = e.len;
            if(dist[to]>dist[v]+len){
                dist[to] = dist[v]+len;
                pq.push({dist[v]+len,to});
            }

        }
    }
    for(int i=1;i<=n;i++){
        if(dist[i]!=1e16)
            cout<<dist[i]<<" ";
        else
            cout<<-1<<" ";
    }
    return 0;
}

多源最短路

Floyd

目前有n个点，对于从i到j的最短距离，考虑从其他点中转会不会让距离变得更短，使用dp。

状态转移方程如下：
想象一个中转圈，从第一个点开始，$k$逐渐扩大，圈的范围逐渐变大，$dp[k][i][j]$表示在前$k$个中转点组成的中转圈下，从$i$到$j$的最短距离。那么如果需要加入一个新的中转点，加入后从$i$到$j$的最短距离必定会从原有的最小值与考虑新中转后的最小值得到。

那么第k个点加入中转后如何计算新中转下的最小值呢？

如果不需要走这个点中转，自然无需多言。如果需要走这个点中转，那么代表从i到j中间肯定经过第k个点，那么其最短路必定从目前的$i-k$最短路与$k-j$最短路得出。

而目前的$i-k$最短路与$k-j$最短路正是$dp[k-1][i][k]与dp[k-1][k][j]$。

如何证明这个思路是完备的呢？

可以从归纳法考虑。

考虑每一对节点的最短路，都会有其max_node。如果max_node是起点或终点，那么在处理max_node为中转之前最短路就已经计算完毕。如果max_node不是终点，那么在处理max_node为中转点的时候，会把最短路分为两条以max_node为起点或者终点的最短路，而这是在之前就被计算出的。

现在我们再来看处理node1为中转的时候是否正确（归纳法初值推理）。当处理node1为中转时，只需考虑有node1中转和直接连接的情况，而在这种情况下，$dp[k][i][j] = \min(dp[k-1][i][j], \ dp[k-1][i][k] + dp[k-1][k][j])$这条公式显然是正确的。

因此，Floyd算法是完备的。

另外需要注意，在编写算法的过程中，可以把dp数组的第一维去掉，因为在
$dp[k][i][j] = \min(dp[k-1][i][j], \ dp[k-1][i][k] + dp[k-1][k][j])$中，如果去掉的第一维，就表示在后续更新时，访问到的可能不是$dp[k-1][i][k]$，而是$dp[k][i][k]$，在01背包问题中，这很重要，但在本次问题中，考虑k为中转和不考虑k为中转，对于起点或终点是节点$k$的路径是完全没有区别的。

蓝桥公园：模板题

代码中，把$k$放在外层循环遍历是为了保证，对于较大的k而言，能保证$dp[i][k]$算出的路径已经全部经过了前面较小$k$的完全中转。如果把$k$放在内层循环，则在访问$dp[1][4]$的时候，需要访问$dp[1][2]$和$dp[2][4]$，此时$dp[2][4]$是没有经过$k$中转的，就会产生错误的结果。而$dp[1][4]$这个错误的结果不会有被更改的机会了。

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
#include<iostream>
#include<cmath>
using namespace std;
long long dp[505][505] = {};
const long long MAXN = 1e18;
int n,m,q;
int main(){
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            dp[i][j] = i==j?0:MAXN;
    for(int i=1;i<=m;i++){
      int u,v,w;
      cin>>u>>v>>w;
      dp[u][v] = min(dp[u][v], (long long)w);
      dp[v][u] = min(dp[v][u], (long long)w);
    }
    for(int k=1;k<=n;k++){
      for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
          dp[i][j] = min(dp[i][j],dp[i][k] + dp[k][j]); //考虑中转
          dp[j][i] = dp[i][j];
        }
      }
    }
    while(q--){
      int a,b;
      cin>>a>>b;
      cout<<((dp[a][b] == MAXN)?-1:dp[a][b])<<endl;
    }
    return 0;
}