斯坦福算法专项课程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算法总会终止,但是由于有负循环,该算法一定不能计算出正确结果(多绕负循环一轮得到的路径长总是更小),所以第二个选项错误,显然第一和第三个选项错误,所以这题第四个选项正确。

编程题

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#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.

参考资料https://www.coursera.org/learn/algorithms-graphs-data-structures/discussions/forums/PbDIsrpzEeaGrAo7bftCxg/threads/MboO0WjgEeiILg7HEO1Trg

设起点为$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