京都大学 情報学研究科 数理工学専攻 2016年8月実施 グラフ理論

标签：

• Kyoto-University
• Shortest-Path-Problem
• Dijkstra-Algorithm

Author

祭音Myyura

Description

大学公表の原題 Let $G=(V,E)$ be a simple strongly connected directed graph. Let $N=[G,w]$ be a network obtained by assigning a nonnegative real weight $w(e)$ to each arc $e \in E$. An arc from vertex u to vertex v is denoted by $(u,v)$, and its weight is also denoted by $w(u,v)$. Define $\text{dist}(u,v)$ as the minimum total weight of a simple directed path from $u$ to $v$ in $N$.

Answer the following questions.

(i) Let $S \subseteq V$ and $s \in S$. Among all arcs $(u,v)$ going from $S$ to $V−S$, choose an arc $(u^*, v^*)$ minimizing

$$\text{dist}(s,u)+w(u,v).$$

Prove that

$$\text{dist}(s,v^∗)=\text{dist}(s,u^∗)+w(u^∗,v^∗).$$

(ii) Show that Dijkstra’s algorithm from a starting vertex $s \in V$ can be implemented in $O(|E| \log |V|)$ time on $N$.

(iii) If one arc with negative weight is added to $N$, the values output by Dijkstra’s algorithm may fail to be correct shortest distances. Construct a concrete example with

$$3\le |V| \le 4$$

and explain how Dijkstra’s algorithm fails.

题目描述

设 $G=(V,E)$ 是简单强连通有向图，网络 $N=[G,w]$ 由给每条弧 $e\in E$ 赋予非负实权 $w(e)$ 得到。用 $(u,v)$ 表示从顶点 $u$ 指向 $v$ 的弧，其权重也记作 $w(u,v)$；$\operatorname{dist}(u,v)$ 定义为 $N$ 中从 $u$ 到 $v$ 的简单有向路的最小总权重。回答：

1. 设 $S\subseteq V$、$s\in S$。在所有从 $S$ 指向 $V\setminus S$ 的弧 $(u,v)$ 中，选取使
   $$\operatorname{dist}(s,u)+w(u,v)$$
   最小的 $(u^*,v^*)$。证明
   $$\operatorname{dist}(s,v^*)= \operatorname{dist}(s,u^*)+w(u^*,v^*).$$
2. 证明以任意 $s\in V$ 为起点的 Dijkstra 算法可在 $N$ 上实现为 $O(|E|\log|V|)$ 时间。
3. 若在 $N$ 中加入一条负权弧，Dijkstra 算法的输出可能不再是正确的最短距离。构造一个满足 $3\le |V|\le4$ 的具体例子，并说明算法如何失效。

Kai

(i)

Take a shortest path from $s$ to $u^*$, and then append the arc $(u^*, v^*)$. If this walk repeats vertices, we may delete cycles. Since all edge weights are nonnegative, deleting cycles cannot increase the total weight. Hence there is a simple path from $s$ to $v^*$ of weight at most

$$\text{dist}(s,u^∗)+w(u^∗,v^∗).$$

i.e.,

$$\text{dist}(s,v^∗) \le \text{dist}(s,u^∗)+w(u^∗,v^∗).$$

Now we prove the reverse inequality.

Let $P$ be a shortest simple path from $s$ to $v^*$. Since $s \in S$ and $v^* \in V - S$, the path $P$ must cross from $S$ to $V−S$ at least once.

Let $(x,y)$ be the first arc of $P$ that goes from $S$ to $V−S$. Thus $x \in S$ and $y \in V−S$. The part of $P$ from $s$ to $x$ has weight at least $\text{dist}(s,x)$. Also, all edge weights after $y$ are nonnegative. Hence

$$\text{dist}(s, v^*) \ge \text{dist}(s, x) + w(x, y)$$

By the choice of $(u^*, v^*)$,

$$\text{dist}(s,u^∗)+w(u^∗,v^∗) \le \text{dist}(s, x) + w(x, y)$$

Hence,

$$\text{dist}(s, v^*) \ge \text{dist}(s,u^∗)+w(u^∗,v^∗)$$

Combining the two inequalities, we get

$$\text{dist}(s,v^∗)=\text{dist}(s,u^∗)+w(u^∗,v^∗).$$

(ii)

Use an adjacency-list representation and a binary heap priority queue supporting Extract-Min and Decrease-Key, the pseudocode of Dijkstra algorithm is given as follows:

Dijkstra(G, w, s):

    for each vertex v in V:
        d[v] = infinity
        parent[v] = NIL

    d[s] = 0

    S = empty set
    Q = priority queue containing all vertices v, keyed by d[v]

    while Q is not empty:

        u = Extract-Min(Q)

        add u to S
        // At this moment, d[u] is fixed.
        // It will never be changed again.

        for each outgoing arc (u, v) in Adj[u]:

            if v is not in S:
                if d[v] > d[u] + w(u, v):
                    d[v] = d[u] + w(u, v)
                    parent[v] = u
                    Decrease-Key(Q, v, d[v])

    return d, parent

For the time complexity

• Each vertex is extracted from the priority queue once: $O(|V| \log |V|)$
• Each arc is relaxed once, and each successful relaxation causes a priority queue update: $O(|E| \log |V|)$

As the directed graph is strongly connected, we have $|E| \geq |V|$ when $|V| \ge 2$.

Thus the total running time is

$$O(|V| \log |V|) + O(|E| \log |V|) = O(|E| \log |V|)$$

(iii)

The true shortest distance from $s$ to $a$ is $2 + (-3) = -1$ using the path $s \to b \to a$.

Now run Dijkstra’s algorithm from $s$.

Initially,

$$\text{dist}(s) = 0, \text{dist}(a) = \infty, \text{dist}(b) = \infty.$$

After processing $s$,

$$\text{dist}(a) = 1, \text{dist}(b) = 2.$$

Dijkstra chooses a next because $\text{dist}(a) = 1 < \text{dist}(b) = 2$. It fixes $\text{dist}(a) = 1$, but the true distance is $\text{dist}(a) = -1$.

Therefore Dijkstra’s algorithm fails when a negative-weight edge is allowed.