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)
# 負の重みの閉路があります。
想定通りの結果を得ることができました。