京都大学 情報学研究科 知能情報学専攻 2023年2月実施 基礎科目 F2-2

标签：

• Kyoto-University
• Bellman-Ford-Algorithm
• Shortest-Path-Problem
• Algorithm-Complexity

Author

祭音Myyura (co-authored with GPT 5.6 SOL)

Description

Let $G=(V,E)$ be a simple directed graph with $V=\{v_1,\ldots,v_n\}$ and $m=|E|$. Every edge $(v_i,v_j)$ has a positive integer weight $d(v_i,v_j)$. The following algorithm computes shortest-path weights from $v_1$:

for i = 1 to n do
    D[i] = +infinity
    P[i] = -1
D[1] = 0
P[1] = 0

for k = 1 to n - 1 do
    for every (vi, vj) in E do
        if D[j] > D[i] + d(vi, vj) then
            D[j] = D[i] + d(vi, vj)
            P[j] = i

1. Let $n=4$, $E=\{(v_1,v_2),(v_1,v_3),(v_2,v_4)\}$, and let every edge weight be $1$. Give $D[1],\ldots,D[4]$ after the algorithm.
2. Assuming an edge weight is obtained in $O(1)$ time, analyze the running time.
3. Explain how to output a shortest path from $v_1$ to a specified $v_i$ using $P$, or No Path if none exists.
4. Let $\operatorname{minrep}(G)$ be the minimum number of outer-loop repetitions that guarantees all shortest-path weights for every ordering of $E$. All edge weights are $1$. Construct $E$ for each case:
   1. $m=n(n-1)-1$ and $\operatorname{minrep}(G)=2$;
   2. $m=n(n-1)/2+(n-1)$ and $\operatorname{minrep}(G)=n-1$.

题目描述

设 $G=(V,E)$ 为简单有向图，$V=\{v_1,\ldots,v_n\}$，$m=|E|$，每条边 $(v_i,v_j)$ 的权 $d(v_i,v_j)$ 均为正整数。题给对所有边重复松弛 $n-1$ 轮的 Bellman-Ford 主体代码，数组 $D$ 保存最短距离，$P$ 保存前驱。

1. 当 $n=4$、$E=\{(v_1,v_2),(v_1,v_3),(v_2,v_4)\}$ 且边权全为 $1$ 时，求算法结束后的 $D[1],\ldots,D[4]$。
2. 设边权可在 $O(1)$ 时间取得，分析算法时间复杂度。
3. 说明如何利用 $P$ 输出从 $v_1$ 到指定 $v_i$ 的一条最短路；不存在时输出 No Path。
4. 记 $\operatorname{minrep}(G)$ 为对任意边扫描顺序都能保证求出全部最短距离所需的最少外层轮数。在边权全为 $1$ 时，分别构造：
   1. $m=n(n-1)-1$、$\operatorname{minrep}(G)=2$ 的图；
   2. $m=n(n-1)/2+(n-1)$、$\operatorname{minrep}(G)=n-1$ 的图。

Kai

Q.1

The shortest paths are the direct edges to $v_2,v_3$ and the path $v_1\to v_2\to v_4$. Hence

$$\boxed{(D[1],D[2],D[3],D[4])=(0,1,1,2)}.$$

Q.2

Initialization takes $\Theta(n)$ time. The algorithm then scans all $m$ edges in each of $n-1$ repetitions, and each relaxation takes $O(1)$ time. Thus

$$\boxed{T(n,m)=\Theta(n+nm)=\Theta(nm)}$$

for $m\ge1$.

Q.3

If $P[i]=-1$, output No Path. Otherwise, follow the predecessor indices backward and use a stack to reverse their order:

OUTPUT-PATH(i):
    if P[i] == -1:
        output "No Path"
        return

    S = empty stack
    u = i
    while u != 1:
        push u onto S
        u = P[u]

    output v1
    while S is not empty:
        output v(pop(S))

Every assignment $P[j]=i$ is made together with a relaxation through $(v_i,v_j)$, so these predecessor edges reconstruct a shortest path.

Q.4

(i)

For $n\ge3$, take the complete simple directed graph and delete only $(v_1,v_n)$:

$$\boxed{ E=\{(v_i,v_j)\mid 1\le i,j\le n, i\ne j\} \setminus\{(v_1,v_n)\}. }$$

Its edge count is $n(n-1)-1$. After one complete scan, every $v_i$ with $2\le i\le n-1$ has distance $1$; during the second scan, an edge $(v_i,v_n)$ sets $D[n]=2$. Thus two scans always suffice.

They are sometimes necessary: order every edge entering $v_n$ before all edges leaving $v_1$. Then no predecessor of $v_n$ is reachable when those entering edges are scanned in the first repetition, so $D[n]$ remains infinite until the second repetition. Therefore

$$\boxed{\operatorname{minrep}(G)=2}.$$

(ii)

Take all edges directed from a higher index to a lower index, together with the forward chain:

$$\boxed{ E=\{(v_j,v_i)\mid 1\le i<j\le n\} \cup\{(v_i,v_{i+1})\mid1\le i<n\}. }$$

The two sets are disjoint, so

$$|E|=\frac{n(n-1)}2+(n-1).$$

The only way to reach a larger-indexed vertex from $v_1$ is along the forward chain. If those chain edges are scanned in reverse order,

$$(v_{n-1},v_n),(v_{n-2},v_{n-1}),\ldots,(v_1,v_2),$$

only one new chain vertex becomes reachable per repetition. Thus $v_n$ needs $n-1$ repetitions. Bellman--Ford always propagates a shortest simple path of at most $n-1$ edges within $n-1$ repetitions, so

$$\boxed{\operatorname{minrep}(G)=n-1}.$$