《算法导论(原书第3版)》第24章部分题目解答

yishujixiaoxiao 2019-12-31

第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

相关推荐