[Python] ベルマン–フォード法

Pythonで、ベルマン–フォード法を使って、重み付きの有向グラフの単一始点最短経路問題を解きます。

以下の続きです。

ダイクストラ法は辺の重みがゼロ以上の場合でしたが、ベルマン–フォード法は辺の重みが負の場合に使われます。

負の閉路がある場合は最短経路を出すことはできませんが、負の閉路の存在を答えることができます。

ベルマン–フォード法

ベルマン–フォード法 (英: Bellman–Ford algorithm) は、重み付き有向グラフにおける単一始点の最短経路問題を解くラベル修正アルゴリズム^[1]の一種である。各辺の重みは負数でもよい。辺の重みが非負数ならば優先度付きキューを併用したダイクストラ法の方が速いので、ベルマン–フォード法は辺の重みに負数が存在する場合に主に使われる
出典: フリー百科事典『ウィキペディア（Wikipedia）』

以下のようなグラフの探索を行います。

最初のグラフは、ダイクストラ法で用いたのと同じグラフです。

a を出発地点、e を目的地とした場合、最短経路は「a -> c -> b -> e」、移動距離は7になるはずです。

2つ目のグラフは、負の重みの辺を持つグラフです。

a を出発点、d を目的地とすると、ベルマン–フォード法により、a から d への最短移動経路: [‘a’, ‘b’, ‘e’, ‘d’] 、移動距離は -2 になるはずです。

3つ目は負の閉路のあるグラフです。

b -> e -> d の移動の総和が -1 と負の閉路を形成しています。

ベルマン–フォード法で最短経路を出すことはできませんが、負の重みの閉路を検出することができるはずです。

import heapq
import sys

class Vertex(object):
    def __init__(self, id):
        self.id = id
        self.adjacent = {}
        self.distance = sys.maxsize
        self.visited = False
        self.previous = None
    
    def __lt__(self, other):
        return self.distance < other.distance

    def add_neighbor(self, neighbor, weight=0):
        self.adjacent[neighbor] = weight
    
    def get_neighbors(self):
        return self.adjacent

    def get_connections(self):
        return self.adjacent.keys()  

    def get_vertex_id(self):
        return self.id

    def get_weight(self, neighbor):
        return self.adjacent[neighbor]
    
    def set_distance(self, distance):
        self.distance = distance

    def get_distance(self):
        return self.distance

    def set_previous(self, previous_vertex):
        self.previous = previous_vertex 
    
    def get_previous(self):
        return self.previous
    
    def set_visited(self):
        self.visited= True


class Graph(object):
    def __init__(self):
        self.vertex_dict = {}
        self.num_vertex = 0
    
    def __iter__(self):
        return iter(self.vertex_dict.values())

    def __len__(self):
        return self.num_vertex

    def add_vertex(self, id):
        self.num_vertex = self.num_vertex + 1
        new_vertex = Vertex(id)
        self.vertex_dict[id] = new_vertex
        return new_vertex

    def get_vertex(self, id):
        if id in self.vertex_dict:
            return self.vertex_dict[id]
        else:
            return None

    def add_edge(self, frm, to, weight=0):
        if frm not in self.vertex_dict:
            self.add_vertex(frm)
        if to not in self.vertex_dict:
            self.add_vertex(to)
        self.vertex_dict[frm].add_neighbor(self.vertex_dict[to], weight)

    def get_vertices(self):
        return self.vertex_dict.keys()

    def get_edges(self):
        edges = []
        for v in self.vertex_dict.values():
            for w in v.get_connections():
                vid = v.get_vertex_id()
                wid = w.get_vertex_id()
                edges.append((vid, wid, v.get_weight(w)))
        return edges


def dijkstra(graph, source, destination):
    source.set_distance(0)

    priority_queue = [(vertex.get_distance(), vertex) for vertex in graph]
    heapq.heapify(priority_queue)

    while len(priority_queue):
        nearest_vrtex = heapq.heappop(priority_queue)
        current = nearest_vrtex[1]
        current.set_visited()

        for next in current.adjacent:
            if next.visited:
                continue
            new_distance = current.get_distance() + current.get_weight(next)

            if next.get_distance() > new_distance:
                next.set_distance(new_distance)
                next.set_previous(current)
                heapq.heappush(priority_queue, (next.get_distance(), next))

    print('dijkstra:')        
    for vertex in graph.vertex_dict.values():
        print(f'{source.get_vertex_id()} から {vertex.get_vertex_id()} への移動距離: {vertex.get_distance()}')

    shortest_path = [destination.get_vertex_id()]
    while destination.previous:
        shortest_path.append(destination.previous.get_vertex_id())
        destination = destination.previous
    print(f'{source.get_vertex_id()} から {vertex.get_vertex_id()} への最短移動経路:', shortest_path[::-1])


def bellman_ford(graph, source, destination):
    # 初期化
    source.set_distance(0)

    # 辺の緩和を反復
    for _ in range(len(graph) - 1):
        for u in graph:
            for v in u.adjacent:
                if v.get_distance() > u.distance + u.get_weight(v):
                    v.set_distance(u.distance + u.get_weight(v))
                    v.set_previous(u)
    
    print('bellmanford:')
    # 負の重みの閉路がないかチェック
    for u in graph:
        for v in u.adjacent:
            if v.get_distance() > u.distance + u.get_weight(v):
                print('負の重みの閉路があります。')
                return
        
    for vertex in graph.vertex_dict.values():
        print(f'{source.get_vertex_id()} から {vertex.get_vertex_id()} への移動距離: {vertex.get_distance()}')

    shortest_path = [destination.get_vertex_id()]
    while destination.previous:
        shortest_path.append(destination.previous.get_vertex_id())
        destination = destination.previous
    print(f'{source.get_vertex_id()} から {vertex.get_vertex_id()} への最短移動経路:', shortest_path[::-1])



if __name__ == '__main__':

    graph_no_neg_edges = Graph()
    graph_no_neg_edges.add_vertex('a')
    graph_no_neg_edges.add_vertex('b')
    graph_no_neg_edges.add_vertex('c')
    graph_no_neg_edges.add_vertex('d')
    graph_no_neg_edges.add_vertex('e')
    graph_no_neg_edges.add_edge('a', 'b', 4)  
    graph_no_neg_edges.add_edge('a', 'c', 1)
    graph_no_neg_edges.add_edge('b', 'e', 4)
    graph_no_neg_edges.add_edge('c', 'b', 2)
    graph_no_neg_edges.add_edge('c', 'd', 4)
    graph_no_neg_edges.add_edge('d', 'e', 4)

    source = graph_no_neg_edges.get_vertex('a')
    destination = graph_no_neg_edges.get_vertex('e')
    dijkstra(graph_no_neg_edges, source, destination)
    bellman_ford(graph_no_neg_edges, source, destination)
    # dijkstra、bellmanford ともに同じ結果
    # a から a への移動距離: 0
    # a から b への移動距離: 3
    # a から c への移動距離: 1
    # a から d への移動距離: 5
    # a から e への移動距離: 7
    # a から e への最短移動経路: ['a', 'c', 'b', 'e']

    graph_neg_edges = Graph()
    graph_neg_edges.add_vertex('a')
    graph_neg_edges.add_vertex('b')
    graph_neg_edges.add_vertex('c')
    graph_neg_edges.add_vertex('d')
    graph_neg_edges.add_vertex('e')
    graph_neg_edges.add_edge('a', 'b', -1)  
    graph_neg_edges.add_edge('a', 'c', 4)
    graph_neg_edges.add_edge('b', 'c', 3)
    graph_neg_edges.add_edge('b', 'd', 2)
    graph_neg_edges.add_edge('b', 'e', 2)
    graph_neg_edges.add_edge('d', 'b', 1)
    graph_neg_edges.add_edge('d', 'c', 5)
    graph_neg_edges.add_edge('e', 'd', -3)

    source = graph_neg_edges.get_vertex('a')
    destination = graph_neg_edges.get_vertex('d')
    bellman_ford(graph_neg_edges, source, destination)
    # a から a への移動距離: 0
    # a から b への移動距離: -1
    # a から c への移動距離: 2
    # a から d への移動距離: -2
    # a から e への移動距離: 1
    # a から d への最短移動経路: ['a', 'b', 'e', 'd']

    graph_neg_edges_neg_cycle = Graph()
    graph_neg_edges_neg_cycle.add_vertex('a')
    graph_neg_edges_neg_cycle.add_vertex('b')
    graph_neg_edges_neg_cycle.add_vertex('c')
    graph_neg_edges_neg_cycle.add_vertex('d')
    graph_neg_edges_neg_cycle.add_vertex('e')
    graph_neg_edges_neg_cycle.add_edge('a', 'b', -1)  
    graph_neg_edges_neg_cycle.add_edge('a', 'c', 4)
    graph_neg_edges_neg_cycle.add_edge('b', 'c', 3)
    graph_neg_edges_neg_cycle.add_edge('b', 'd', 2)
    graph_neg_edges_neg_cycle.add_edge('b', 'e', 2)
    graph_neg_edges_neg_cycle.add_edge('d', 'b', 0)
    graph_neg_edges_neg_cycle.add_edge('d', 'c', 5)
    graph_neg_edges_neg_cycle.add_edge('e', 'd', -3)

    source = graph_neg_edges_neg_cycle.get_vertex('a')
    destination = graph_neg_edges_neg_cycle.get_vertex('d')
    bellman_ford(graph_neg_edges_neg_cycle, source, destination)
    # 負の重みの閉路があります。

想定通りの結果を得ることができました。