[グラフ] DAGの最短経路

ベルマンフォード法 ベルマン–フォード法(英:Bellman–Ford algorithm) は、重み付き有向グラフにおける単一始点の最短経路問題を解くラベル修正アルゴリズムの一種である。各辺の重みは負数でもよい。辺の重みが非負数ならば優先度付きキュー...

DAG

DAG とは Directed acyclic graph 有向非巡回グラフの略で、閉路のない有向グラフのことです。

有向非巡回グラフ有向非循環グラフ有向無閉路グラフ(ゆうこうひじゅんかいグラフ、: Directed acyclic graph, DAG)とは、グラフ理論における閉路のない有向グラフのことである。有向グラフは頂点と有向辺(方向を示す矢印付きの辺)からなり、辺は頂点同士をつなぐが、ある頂点 \(v\) から出発し、辺をたどり、頂点 \(v\) に戻ってこないのが有向非巡回グラフである[1][2][3]

出典: フリー百科事典『ウィキペディア(Wikipedia)』

DAG であれば、トポロジカルソートを使うことで、ダイクストラ法やベルマンフォード法より速く、\( O(V + E)\)で最短経路を求めることができます。

トポロジカルソート

トポロジカルソート: topological sort)とは、グラフ理論において、有向非巡回グラフ: directed acyclic graph, DAG)の各ノードを順序付けして、どのノードもその出力辺の先のノードより前にくるように並べることである。有向非巡回グラフは必ずトポロジカルソートすることができる。

出典: フリー百科事典『ウィキペディア(Wikipedia)』

DAGでなので、「入力辺を持たないノード」は開始ノードになります。

「入力辺を持たないノード」から隣接ノードへのエッジを削除します。

もし隣接ノードが他に入力エッジを持たない場合は、この隣接ノードは開始ノードに続くノードと判断できます。

トポロジカルソートの計算量は\(O(V+E)\)です。

トポロジカルソートを Python で書きます。 以下の続きです。 トポロジカルソート トポロジカルソート(英:topological sort)とは、グラフ理論において、有向非巡回グラフ(英:directed acyclic graph, DA...

以下のグラフ (a) をトポロジカルソートしてみます。

import collections
import sys


class Node(object):

    def __init__(self, name):
        self.name = name
        self.indegree = 0
        self.adjacency_list = []
        self.predecessor = None
        

class ShortestPathDAG(object):

    def __init__(self, nodes):
        self.nodes = nodes
        self.topological_sorted_list = []

    def topological_sort(self):

        queue = collections.deque()

        for node in self.nodes:
            if node.indegree == 0:
                queue.append(node)

        while queue:
            current_node = queue.popleft()
            self.topological_sorted_list.append(current_node)
            for neighbor, weight in current_node.adjacency_list:
                neighbor.indegree -= 1
                if neighbor.indegree == 0:
                    queue.append(neighbor)

        if len(self.nodes) != len(self.topological_sorted_list):
            raise Exception('Not DAG')


if __name__ == '__main__':
    r = Node('r')
    s = Node('s')
    t = Node('t')
    x = Node('x')
    y = Node('y')
    z = Node('z')

    r.indegree = 0
    r.adjacency_list.extend([(t, 3), (s, -1)])
    s.indegree = 1
    s.adjacency_list.extend([(t, 2), (x, 6)])
    t.indegree = 2
    t.adjacency_list.extend([(x, 7), (y, 4)])
    x.indegree = 2
    x.adjacency_list.extend([(y, 5), (z, 1)])
    y.indegree = 2
    y.adjacency_list.extend([(z, -2)])
    z.indegree = 2
    z.adjacency_list.extend([])

    nodes = [r, s, t, x, y, z]
    shortest_path_dag = ShortestPathDAG(nodes)
    shortest_path_dag.topological_sort()

    # r s t x y z 
    for node in shortest_path_dag.topological_sorted_list:
        print(node.name, end=' ')

DAGの最短経路

トポロジカルソート後の最短経路の計算は簡単に行えます。

開始地点の最短距離を0、その他を無限大に設定し、トポロジカルソート順に最短距離の更新を行うだけです。

計算量は\(O(V+E)\)です。

有向非巡回グラフ: 深さ優先探索

以下のグラフ(b) を探索します。

import collections
import sys


class Node(object):

    def __init__(self, name):
        self.name = name
        self.indegree = 0
        self.adjacency_list = []
        self.min_distance = sys.maxsize
        self.predecessor = None
        

class ShortestPathDAG(object):

    def __init__(self, start_node, nodes):
        self.start_node = start_node
        self.nodes = nodes
        self.topological_sorted_list = []

    def _topological_sort(self):

        queue = collections.deque()

        for node in self.nodes:
            if node.indegree == 0:
                queue.append(node)

        while queue:
            current_node = queue.popleft()
            self.topological_sorted_list.append(current_node)
            for neighbor, _ in current_node.adjacency_list:
                neighbor.indegree -= 1
                if neighbor.indegree == 0:
                    queue.append(neighbor)

        if len(self.nodes) != len(self.topological_sorted_list):
            raise Exception('Not DAG')

    def calculate_shoretest_path(self):
        self._topological_sort()
        self.start_node.min_distance = 0

        for node in self.topological_sorted_list:
            for neighbor, weight in node.adjacency_list:
                temp_distance = node.min_distance + weight
                if temp_distance < neighbor.min_distance:
                    neighbor.min_distance = temp_distance
                    neighbor.predecessor = node
                    
    def show_shotest_path(self, goal):
        current_node = goal
        order_list = []
        while current_node is not None:
            order_list.append(current_node.name)
            current_node = current_node.predecessor
        print(f'from {self.start_node.name} to {goal.name} distance {goal.min_distance}', order_list[::-1])


if __name__ == '__main__':
    r = Node('r')
    s = Node('s')
    t = Node('t')
    x = Node('x')
    y = Node('y')
    z = Node('z')

    r.indegree = 0
    r.adjacency_list.extend([(s, 5), (t, 3)])
    s.indegree = 1
    s.adjacency_list.extend([(t, 2), (x, 6)])
    t.indegree = 2
    t.adjacency_list.extend([(x, 7), (y, 4), (z, 2)])
    x.indegree = 2
    x.adjacency_list.extend([(y, -1), (z, 1)])
    y.indegree = 2
    y.adjacency_list.extend([(z, -2)])
    z.indegree = 3
    z.adjacency_list.extend([])

    nodes = [r, s, t, x, y, z]
    shortest_path_dag = ShortestPathDAG(s, nodes)
    shortest_path_dag.calculate_shoretest_path()
    # from s to r distance 9223372036854775807 ['r']
    shortest_path_dag.show_shotest_path(r)
    # from s to s distance 0 ['s']
    shortest_path_dag.show_shotest_path(s)
    # from s to t distance 2 ['s', 't']
    shortest_path_dag.show_shotest_path(t)
    # from s to x distance 6 ['s', 'x']
    shortest_path_dag.show_shotest_path(x)
    # from s to y distance 5 ['s', 'x', 'y']
    shortest_path_dag.show_shotest_path(y)
    # from s to z distance 3 ['s', 'x', 'y', 'z']
    shortest_path_dag.show_shotest_path(z)

想定通りの結果になりました。

最長経路問題

最長経路問題はNP完全問題です。

最短経路とは逆の問題で、最長単純道問題もある。最短経路の場合は、最短経路の部分問題もやはり最短経路であるが、最長単純道の場合、部分構造最適性が成立しておらず、貪欲法などで解くことが出来ない。辺の重みなしであっても、NP完全問題である。

出典: フリー百科事典『ウィキペディア(Wikipedia)』

しかし、DAGであればトポロジカルソートを使う最短経路とほぼ同様な考え方で解くことができます。

Longest Path in a Directed Acyclic Graph

以下のスライドがダントツで分かりやすいです。 素集合データ構造 素集合データ構造(そしゅうごうデータこうぞう、英: disjoint-set data structure)は、データの集合を素集合(互いにオーバーラップしない集合)に分割し...