PythonでAizu Online Judgeを解く/GRL_1_B - Single Source Shortest Path (Negative Edges)

Posted on

概要

重み付きの有向グラフ \(G(V, E)\) が与えられます。頂点 \(r\) を始点としたときの各頂点までの最短経路の長さを出力してください。ただし、グラフは負辺を含む場合があるものとします。

問題URL:
https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/1/GRL_1_B

制約

\(1 \leq |V| \leq 1000\)
\(0 \leq |E| \leq 2000\)
\(-10000 \leq d_i \leq 10000\)
グラフ \(G\) は平行辺を持たない
グラフ \(G\) は自己ループを持たない

入力

%python
def input(f):
    global v, e, r, s, t, d, g
    
    v, e, r = map(int, f.readline().split())
    s = []
    t = []
    d = []
    for _ in range(e):
        s_, t_, d_ = map(int, f.readline().split())
        s.append(s_)
        t.append(t_)
        d.append(d_)
        
    g = [list() for _ in range(v)]
    for i in range(e):
        g[s[i]].append(i)

サンプル入力

%sh
cat << EOF > /tmp/input1
4 5 0
0 1 2
0 2 3
1 2 -5
1 3 1
2 3 2
EOF

cat << EOF > /tmp/input2
4 6 0
0 1 2
0 2 3
1 2 -5
1 3 1
2 3 2
3 1 0
EOF

cat << EOF > /tmp/input3
4 5 1
0 1 2
0 2 3
1 2 -5
1 3 1
2 3 2
EOF

Python: 入力をnetworkxで可視化してみる

%sh
pip install networkx

Collecting networkx
  Downloading https://files.pythonhosted.org/packages/f3/f4/7e20ef40b118478191cec0b58c3192f822cace858c19505c7670961b76b2/networkx-2.2.zip (1.7MB)
Collecting decorator>=4.3.0 (from networkx)
  Downloading https://files.pythonhosted.org/packages/bc/bb/a24838832ba35baf52f32ab1a49b906b5f82fb7c76b2f6a7e35e140bac30/decorator-4.3.0-py2.py3-none-any.whl
Building wheels for collected packages: networkx
  Running setup.py bdist_wheel for networkx: started
  Running setup.py bdist_wheel for networkx: finished with status 'done'
  Stored in directory: /root/.cache/pip/wheels/68/f8/29/b53346a112a07d30a5a84d53f19aeadaa1a474897c0423af91
Successfully built networkx
Installing collected packages: decorator, networkx
Successfully installed decorator-4.3.0 networkx-2.2
You are using pip version 9.0.1, however version 18.1 is available.
You should consider upgrading via the 'pip install --upgrade pip' command.

%python
import os

if os.environ.get('ZEPPELIN_HOME'):
    import networkx as nx
    import matplotlib.pyplot as plt
    
    def visualize():
        G = nx.MultiDiGraph()
        for i in range(v):
            G.add_node(i, node_color='b')
        for i in range(e):
            G.add_edge(s[i], t[i], t=d[i])
        
        plt.figure()
        plt.style.use('seaborn')
        plt.axis("off")
        pos = nx.spring_layout(G)
        nodes_without_r = [i for i in range(v)]
        nodes_without_r.remove(r)
        nodes = nx.draw_networkx_nodes(G, pos, nodelist=nodes_without_r, node_color='w', linewidths=2)
        nodes.set_edgecolor('black')
        nodes = nx.draw_networkx_nodes(G, pos, nodelist=[r], node_color='red', linewidths=2)
        nodes.set_edgecolor('black')
        nx.draw_networkx_labels(G, pos)
        nx.draw_networkx_edges(G, pos)
        nx.draw_networkx_edge_labels(G, pos)
        plt.show()

%python
if os.environ.get('ZEPPELIN_HOME'):
    with open('/tmp/input1') as f:
        print('Example #1')
        input(f)
        visualize()

Example #1

この場合は各頂点について最短経路を求めることができます。

%python
if os.environ.get('ZEPPELIN_HOME'):
    with open('/tmp/input2') as f:
        print('Example #2')
        input(f)
        visualize()

Example #2

この場合は、0 => 1 => 2 => 3 => 1 => ... のように辿り続けることでコストを下げ続けることができるので最短経路は求まりません。

%python
if os.environ.get('ZEPPELIN_HOME'):
    with open('/tmp/input3') as f:
        print('Example #3')
        input(f)
        visualize()

Example #3

頂点1から0に移動することはできません。

考え方

Bellman–Ford Algorithm

GRL_1_Aと同じ問題にみえますが今回はグラフが負辺を含むため前回のやり方では無限ループに陥ってしまうことがあります（例: 負の閉路が存在する場合）。このようなグラフで最短経路を求めるには1950年代に考案された Bellman–Ford 法と呼ばれるアプローチを利用すると良いそうです。

このアルゴリズムでは頂点の回数だけ最小コストの更新処理を繰り返し、途中で最小コストの更新が発生しなくなったら答えが求まっているものとし、そうでなければグラフは負閉路を含んでいて無限に更新を続けることができるものとして扱います。これにより \(\mathcal{O}(|V| \cdot |E|)\) 程度の計算量で最短経路を求めることができます。

実装

%python
import sys


def init():
    global inf, mincost
    inf = sys.maxint
    mincost = [inf]*v
    mincost[r] = 0

def update():
    updated = False
    for i in range(e):
        if mincost[s[i]] is not inf:
            c = mincost[s[i]] + d[i]
            if mincost[t[i]] > c:
                mincost[t[i]] = c
                updated = True
                
    return updated

def solve():
    init()
    
    flag = True
    for i in range(v):
        if not update():
            flag = False
            break
    
    if flag:
        print('NEGATIVE CYCLE')
    else:
        for x in mincost:
            if x is inf:
                print('INF')
            else:
                print(x)

Example Output #1

%python
if os.environ.get('ZEPPELIN_HOME'):
    os.environ['INPUT'] = '/tmp/input1'

with open(os.environ.get('INPUT') or '/dev/stdin') as f:
    input(f)
    solve()

0
2
-3
-1

Example Output #2

%python
if os.environ.get('ZEPPELIN_HOME'):
    os.environ['INPUT'] = '/tmp/input2'

    with open(os.environ.get('INPUT') or '/dev/stdin') as f:
        input(f)
        solve()

NEGATIVE CYCLE

Example Output #3

%python
if os.environ.get('ZEPPELIN_HOME'):
    os.environ['INPUT'] = '/tmp/input3'

    with open(os.environ.get('INPUT') or '/dev/stdin') as f:
        input(f)
        solve()

INF
0
-5
-3

%sh
# apt install -y jq
# ~/.aoj/bin/login
curl -s http://localhost:8080/api/notebook/2DTBQV2DF | \
    jq -c -r '.body.paragraphs[].text | select(.|test("^%python"))' | \
    sed 's/^%python//' | \
    ~/.aoj/bin/submit GRL_1_B Python /dev/stdin
exit 1

{"token": "081a5b07-4844-4613-a96f-2a7972090729"}

もうずっと Warshall–Floyd とか Bellman–Ford とか個人名だと思ってたんですが、改めて調べてみると両者とも2名の代表的な考案者にちなんだ名前のアルゴリズムだったみたいです……。ワーシャル・フロイドさんは存在しないっぽい（探したら居そうだけどな）。

%md

--- NO TITLE