第24章 单源最短路径

24.1 Bellman-Ford算法

24.1-4

思路：

先做|V|-1遍松弛操作，然后再做一遍松弛操作，对于这次松弛操作中dist值被更新的点，必然包含了每个负环中的至少一个点。对于这些点做dfs查找它们能够在图中到达哪些点，所有被搜索到的点即为题目要求找的点

部分c++代码：

#include <bits/stdc++.h>
using namespace std;
const int maxn = ...;
const int inf = 0x3f3f3f3f;//正无穷
struct E{
  int x,y,z;//三元组（x,y,z)表示一条有向边。从x出发到y，权值为z。
}
vector<E> es;//存边
vector<int> e[maxn];//模拟邻接链表
vector<int> vec;//存起始点
void bellman(int s){
  for(int i = 1; i<=n; i++)d[i]=inf;
  d[s] = 0;
  for(int t = 1; t<n; t++){
    for(auto e:es){
      if(d[e.x]!=inf && d[e.x]+e.z<d[e.y])d[e.y] = d[e.x] + w;
    }
  }
  for(auto e:es){
    if(d[e.x]!=inf && d[e.x]+e.z<d[e.y]){
      vec.push_back(y);
    }
  }
}
int v[maxn];
void dfs(int x){
  v[x] = 1;
  for(auto y: e){
    if(!v[y]) dfs(y);
  }
}
void solve(int s){
  bellman(s);
  for(auto x:vec){
    if(!v[x]) dfs(x);
  }
  for(int i = 1; i<=n; i++){
    if(v[i]) cout<<"负无穷"<<endl;
    else if(d[i]==inf) cout<<"不可达"<<endl;
    else cout<<d[i]<<endl;
  }
}

24.1-5

思路：

跑一遍Bellman-Ford算法，具体做法如下：
1、初始化\(\forall v\in V ,d[v] = 0\)。
2、对于边（x,y,z)，如果d[y]>d[x]+z，更新d[y]。

证明：

首先，一个点对自身的距离为0，所以\(\forall v\in V,\delta^*(v)\leq 0\)，可以将每个点d[v]初始化为0
接下来证明更行操作的正确性：
设\(\delta_i(u,v)\)为从u到v边数不超过I的路径的最小值\(u,v\in V\)
同时，设\(\delta_i^*(v) = min_{u\in V}\{\delta_i(u,v)\}\)
这样我们便有 \(\delta^*(v)=\delta_{n-1}^*(v)\)
只要我们证明，对于\(0\leq i<n\)，均有\(d[v]\leq \delta_i^*(v)\)且最后\(d[v] = \delta_{n-1}^*(v)\)即可
1、i==0时，\(d[v]\leq \delta^*(v) = 0\)
2、假设前i次迭代中\(d[v]\leq \delta_i^*\)成立
对于第i+1次迭代，
如果\(\delta_{i+1}^* = \delta_{i}^*\)，
\(d[v] \leq \delta_{i+1}^*(v) = \delta_i^*(v)\)仍成立
否则，在此轮中边(u,v)被松弛，有\(d[v] = min\{d[u]+w(u,v)\}\)\(\leq min\{\delta_i^*(u)+w(u,v)\} = \delta_{i+1}^*(v)\)，仍成立。
综上，所以有\(d[v]\leq \delta_{n-1}^*\)
因为d[v]为两顶点路径长，所以\(d[v] = \delta_{n-1}^*(v)\)
（以上证明前提是图中无负环，实际程序中将负环判掉了）

部分c++代码：

#include <bits/stdc++.h>
using namespace std;
const int maxn = ...;
struct E{
  int x,y,z;//三元组（x,y,z)表示一条有向边。从x出发到y，权值为z。
}
vector<E> es;//存边
int d[maxn];
bool bellman(){
  memset(d,0,sizeof(d));
  for(int t = 1; t<n; t++){
    for(auto e:es){
      if(d[e.y]>d[e.x]+z) d[e.y] = d[e.x] + z;
    }
  }
  for(auto e:es){
    if(d[e.y]>d[e.x]+z) return false;
  }
  return true;
}
void solve(){
  if(bellman()){
    for(int i = 1; i<=n; i++)cout<<d[i]<<endl;
  } else{
    cout<<"有负环";
  }
}

24.3 Dijkstra算法

24.3-6

24.3-8

24.3-9

24.3-10