Exercise 1
(⇒) 存在负环 ⇒ 第 $n$ 次迭代必有更新
设 $C$ 是一个负环，权值和 $W<0$。由于所有顶点从 $s$ 可达，存在路径 $P$ 到 $C$ 上某点。绕环无穷次可使路径长度任意小。若第 $n$ 次迭代无更新，则对所有边有 $\mathrm{dist}(v)\le\mathrm{dist}(u)+\ell(u,v)$，即距离已满足三角不等式，不可能再有更短路径，矛盾。故必有更新。
(⇐) 第 $n$ 次迭代有更新 ⇒ 存在负环
设第 $n$ 次迭代中边 $(u,v)$ 使 $\mathrm{dist}_{n-1}(u)+\ell(u,v)<\mathrm{dist}_{n-1}(v)$。更新后得到一条从 $s$ 到 $v$ 的路径，边数 $L\ge n$（否则前 $n-1$ 次迭代已得该距离）。沿 $\mathrm{prev}$ 回溯 $L\ge n$ 步，由鸽巢原理必有一重复顶点，从而形成环 $R$。因每次更新对应严格不等式，沿环累加得环权和 $<0$，即 $R$ 为负环。
Exercise 2
All-Pairs Shortest Paths Through a Fixed Node
Require: 强连通有向图 $G = (V, E)$，边权为正，指定节点 $v_0 \in V$
Ensure: 矩阵 $dist[u][v]$ 表示从 $u$ 到 $v$ 且必须经过 $v_0$ 的最短路径长度
在原始图 $G$ 上以 $v_0$ 为源点运行 Dijkstra 算法，得到从 $v_0$ 到所有节点的最短距离数组 $d_{out}[v]$
构建反向图 $G^T = (V, E^T)$，其中 $(u,v) \in E^T \iff (v,u) \in E$
在反向图 $G^T$ 上以 $v_0$ 为源点运行 Dijkstra 算法，得到从 $v_0$ 到所有节点的最短距离数组 $d_{in}^T[v]$，则原图中从节点 $v$ 到 $v_0$ 的最短距离为 $d_{in}[v] = d_{in}^T[v]$
for 每对节点 $(u, v) \in V \times V$ do
$dist[u][v] = d_{in}[u] + d_{out}[v]$
end for
return $dist$
时间复杂度是$O(V^2 + (V+E)\log V)$
Exercise 3
有向正权图的最短环
Require: 有向图 $G = (V, E)$，边权为正整数；$|V| = n$
Ensure: 最短环的长度；若图无环，则输出“无环”
初始化距离矩阵 $dist[n][n]$
for every $i \in V$ do
for every $j \in V$ do
if $i = j$ then
$dist[i][j] = 0$
else if $(i,j) \in E$ then
$dist[i][j] = w(i,j)$
else
$dist[i][j] = \infty$
end if
end for
end for
for $k = 1$ to $n$ do
for $i = 1$ to $n$ do
for $j = 1$ to $n$ do
if $dist[i][k] + dist[k][j] < dist[i][j]$ then
$dist[i][j] = dist[i][k] + dist[k][j]$
end if
end for
end for
end for
初始化最短环长度 $cycle\_len = \infty$
for $u = 1$ to $n$ do
for $v = 1$ to $n$ do
if $u \neq v$ and $dist[u][v] < \infty$ and $dist[v][u] < \infty$ then
$cycle\_len = \min(cycle\_len,\; dist[u][v] + dist[v][u])$
end if
end for
end for
if $cycle\_len = \infty$ then
print“无环”
else
print $cycle\_len$
end if
复杂度就是Floyd的$O(n^3)$
Exercise 4
不可以
![[Pasted image 20260425133924.png]]
这个图中，按照题中算法算出来就是A->B最长路是2，但是很明显是3，故这个算法不对
Exercise 5
不能。如果原图中含有的是正环，取负后就变成了负环，此时再用Bellman-Ford就不能输出最短路径，自然就找不到原图上的最长路径。
Exercise 6
对H用Kruskal算法。
先把H中的边排好序，考虑在T中删除$e \in T \cap H$形成两个联通块A,B，由cut property，则e一定是连接这A,B中最小的那条边。
考虑对H用Kruskal算法，在考虑到e之前，选取到的边均在$H \cap A$ 和$H \cap B$里，故e一定会被加入到H的MST里。
对 $\forall e \in T \cap H$均有这个性质，故有 $T \cap H$包含于H的某个MST中。