斯坦福算法专项课程Course2 week2习题解析
这一部分将带来Course2 week2的习题解析。
选择题
选择题1
考虑边长非负且不同，源点为$s$的有向图。固定目标顶点$t$，并假设该图包含至少一个$s-t$路径。
以下哪项陈述属实？
- $s-t$的最短路径必须排除最长边$G$
- $s-t$的最短路径必须有最短边$G$
- $s-t$的最短路径可能有$n-1$条边，$n$是顶点总数
- $s-t$的最短路径没有重复顶点
最短路径和单个边长无关，前两个选项错误。考虑一条直线上$n$个点，从起点到终点有$n-1$条边，第三项正确。假设最短路径有重复顶点，所以包含环，把这个环去掉依旧是$s-t$路径，由边长非负可得，长度更短，第四项正确。
选择题2
考虑边长不同，源点为$s$的有向图，目标顶点$t$的有向图，在什么条件下$s-t$最短路径唯一。
当所有边长都是不同的正整数时，并且图$G$不包含有向循环
当所有边长都是2的不同幂
没有其他选项是正确的
当所有边长都是不同的正整数时
选项1,4可以考虑一个四边形，两条边长为1,4另外两条为2,3，那么最短路径不唯一。当边长为2的不同幂时，可以把最短路径理解为一个二进制数，由二进制数表示的唯一性可得此时最短路径唯一。
选择题3
考虑有向图 $G=(V,E)$ 和一个源点$s$，图具有以下属性：$s$出发的边有任意（可能是负的）长度; 所有其他边长都是非负的; 并且没有任何其他顶点到$s$的边。
Dijkstra的最短路径算法是否正确计算最短路径距离（从$s$出发）在这张图中？
只有我们加上$G$不包含负循环的假设
从不
也许，也许不是（取决于图）
永远正确
由于只有从$s$出发的边，可以考虑给从$s$出发的边加上正常数$M$，使得这些边都为正数，在更新后的图使用Dijkstra算法，最后的结果再减去$M$即可，可以看到，这样得出的结果是正确的，所以选择第四个选项。
选择题4
考虑有向图$G$和源点$s$。假设$G$有一些负边长但没有负循环，这意味着$G$没有定向循环，其中边长的总和为负。假设在此图上运行Dijkstra的算法。以下哪项陈述属实？[检查所有适用。]
在具有负边长的图上运行Dijkstra算法是不可能的
Dijkstra的算法总是终止，在某些情况下，它计算的路径将是$s$到其他顶点的最短路径
Dijkstra的算法可能永远循环
Dijkstra的算法总是终止，但在某些情况下，它计算的路径不是$s$到其他顶点的最短路径
注意Dijkstra算法总会终止，但是由于有负边，正确性不一定能保证，所以第二第四项正确。
选择题5
考虑有向图$G$和源点$s$。假设$G$有一个负循环，这意味着$G$有定向循环，其中边长的总和为负，并且$s$到这个循环有一条路径。假设在此图上运行Dijkstra的算法（起点为$s$）。以下哪项陈述属实？[检查所有适用。]
在具有负边长的图上运行Dijkstra算法是不可能的
Dijkstra的算法总是终止，在某些情况下，它计算的路径将是$s$到其他顶点的最短路径
Dijkstra的算法可能永远循环
Dijkstra的算法总是终止，但在某些情况下，它计算的路径不是$s$到其他顶点的最短路径
注意Dijkstra算法总会终止，但是由于有负循环，该算法一定不能计算出正确结果（多绕负循环一轮得到的路径长总是更小），所以第二个选项错误，显然第一和第三个选项错误，所以这题第四个选项正确。
编程题
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <sstream>
using namespace std;
const int N = 1e6;
const int INFTY = 1e9;
//定义图
vector <int> G[N];
//定义边长
vector <int> G1[N];
//节点数量
int n = 1;
//判断是否访问过
int flag[N];
//距离数组
int dist[N];
int Find_min(){
int index = -1;
int min_dist = INFTY;
for (int i = 1; i <= n; i++){
if (flag[i] == 0 && dist[i] < min_dist){
index = i;
min_dist = dist[i];
}
}
return index;
}
void Dijkstra(int s){
//初始化
for (int i = 1; i <= n; i++){
dist[i] = INFTY;
}
for (int i = 0; i < G[s].size(); i++){
int v = G[s][i];
dist[v] = G1[s][i];
}
flag[s] = 1;
dist[s] = 0;
while(1){
int u = Find_min();
if (u == -1){
break;
}
flag[u] = 1;
//更新
for (int i = 0; i < G[u].size(); i++){
int v = G[u][i];
if (dist[u] + G1[u][i] < dist[v]){
dist[v] = dist[u] + G1[u][i];
}
}
}
}
int main(){
//输入
//文件名
char filename[] = "dijkstraData.txt";
freopen(filename, "r", stdin);
int u, v, d;
string S;
char c;
while (getline(cin, S)){
stringstream ostr(S);
ostr >> u;
n = max(n, u);
while (ostr >> v >> c >> d){
n = max(n, v);
G[u].push_back(v);
G1[u].push_back(d);
}
}
//初始化
memset(flag, 0, sizeof(flag));
int s = 1;
//运行算法
Dijkstra(s);
//显示结果
int m = 10;
int index[m] = {7, 37, 59, 82, 99, 115, 133, 165, 188, 197};
for (int i = 0; i < m; i++){
int u = index[i];
int d = dist[u];
printf("%d: %d\n", u, d);
}
return 0;
}思考题
思考题1
In lecture we define the length of a path to be the sum of the lengths of its edges. Define the bottleneck of a path to be the maximum length of one of its edges. A mininum-bottleneck path between two vertices s and $t$ is a path with bottleneck no larger than that of any other s-t path. Show how to modify Dijkstra’s algorithm to compute a minimum-bottleneck path between two given vertices. The running time should be $O(m \log n)$ as in lecture.
回顾Dijkstra算法
及其快速实现方式
对于这题来说，$A[s]$记录起点到$s$当前的mininum-bottleneck，每一步找到使得下式最小化的点
对于快速实现方式，$\text{key}[s]$的更新条件为
思考题2
We can do better. Suppose now that the graph is undirected. Give a linear-time ($O(m)$) algorithm to compute a minimum-bottleneck path between two given vertices.
设起点为$s$，终点为$t$，minimum-bottleneck为$d$，构造数组$a[]$，均初始化为无穷，构造$G_{\text{rev}}$为反向图（无向图时即原图）。
第一轮，在图$G$中进行BFS：
从$s$开始BFS，对于$u\to v$，作如下更新
如果$v= t$，则
第二轮：在图$G_{\text{rev}}$中进行BFS：
从$t$开始BFS，对于$u\to v$，作如下更新
如果$v= s$，则
思考题3
What if the graph is directed? Can you compute a minimum-bottleneck path between two given vertices faster than $O(m \log n)$?
同思考题2