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

    Posted on 2018/10/10

    概要

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

    制約

    • \(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
    

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