跳到主要内容

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

标签：

Author​

祭音Myyura

Description​

Let be a simple strongly connected directed graph. Let be a network obtained by assigning a nonnegative real weight to each arc . An arc from vertex u to vertex v is denoted by , and its weight is also denoted by . Define as the minimum total weight of a simple directed path from to in .

Answer the following questions.

(i) Let and . Among all arcs going from to , choose an arc minimizing

Prove that

(ii) Show that Dijkstra’s algorithm from a starting vertex can be implemented in time on .

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

and explain how Dijkstra’s algorithm fails.

Kai​

(i)​

Take a shortest path from to , and then append the arc . 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 to of weight at most

i.e.,

Now we prove the reverse inequality.

Let $$Psv^s \in Sv^ \in V - SPSV−S$ at least once.

Let be the first arc of that goes from to . Thus and . The part of from to has weight at least . Also, all edge weights after are nonnegative. Hence

By the choice of ,

Hence,

Combining the two inequalities, we get

(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:
  • Each arc is relaxed once, and each successful relaxation causes a priority queue update:

As the directed graph is strongly connected, we have when .

Thus the total running time is

(iii)​

The true shortest distance from to is using the path .

Now run Dijkstra’s algorithm from .

Initially,

After processing ,

Dijkstra chooses a next because . It fixes , but the true distance is .

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

目录