TL;DR
- グラフの最短ルートを算出するダイクストラ法について学びます。
- グラフ理論で使う、ごく基本的な用語などに関しても触れます。
- 実際にダイクストラ法をPythonで書いて理解を深めます。
今回対象とするグラフと簡単な用語の説明
今回は以下のようなグラフを扱っていきます。駅の路線図のようなものをイメージしてください。
AやBといった部分は頂点（vertex）もくは節点（せってん : node）と呼ばれます。
路線図で言えば止まる駅となります。
各頂点を結ぶ線の部分はエッジ（edge）もしくは辺・枝などと呼ばれます。路線図で言えば駅と駅を結ぶ線路に該当します。
エッジのところに記載してある数字は重み（weight）やコスト（cost）などと呼ばれます。そのエッジを通る際に必要になるコスト的なものになります。路線図で言うと駅と駅の間の距離が該当します。
この今回の記事では頂点間の距離で扱います。
また、グラフには無向グラフ（undirected graph）と有向グラフ（directed graph）があります。
無向グラフは頂点間で進める方向は決まっていません。双方向に進むことができます。
路線図で言えばとある駅での上りと下りといったところでしょうか。
一方で有向グラフは頂点間で一方方向しか進めません。
この記事では無向グラフの内容を扱っていきます。
ダイクストラ法とは
Dijkstra's Algorithm
ダイクストラ法（Dijkstra's Algorithm）とは、グラフの最短経路を算出するためのグラフ理論のアルゴリズムです。
特定の頂点から、さらに別の頂点まででどのように進むと一番距離が短くなるのかがアルゴリズムで算出されます。
少し前に書いた記事（PythonでA*（A-star）アルゴリズムを書く）で触れたA*アルゴリズムに近い内容になります（ヒューリスティックなどの差異があるものの）。
今回Pythonで解く問題
少し前に触れた以下のグラフの、頂点Aから頂点Jまでの最短経路をPythonで算出します。
ダイクストラ法の計算内容
- [1]. スタートの頂点を決めます。
- [2]. その頂点に隣接している頂点に対する、スタートの頂点からの距離をリストなどへ格納します。
- また、その際に隣接する頂点に対する、そこへ至ったエッジの参照を保持します。
- [3]. 次に隣接する頂点に移り、その頂点に隣接している頂点へのスタートの頂点からの距離を格納します。
- その際に、もし既に隣接する頂点のスタートの頂点からの距離が格納されていれば（別ルートで対象の頂点までの距離の計算がされていれば）、距離が短くなる場合のみ格納されている距離の値を更新します。
- 距離が更新される場合には、[2]で保持したその頂点に至るエッジの参照も更新します。
- [4]. [3]を繰り返して、対象が無くなる（全てのルートの計算が終わる）まで計算を繰り返します。
計算が終わった後は、スタートの頂点から任意の頂点への最短距離を出したい場合には、各頂点でその頂点に至るのに最短となる直前のエッジの参照は保持してあるので、最終ゴールの頂点から順番にエッジを参照して頂点をスタートの頂点になるまでさかのぼっていって、そのルートを反転させれば最短経路が出せます。
文字だけだと分かりづらいので少し図で触れてみます。まずは[1]と[2]の部分です。
赤字の部分が計算のイテレーションで算出される距離です。まずはAの頂点からスタートしていきます。
Aの頂点からAの頂点への当たり前ですが距離は0となります。
[2]で必要なAに隣接するBとEの頂点に距離とその頂点に至るエッジを保持します。
まだこの段階では他の経路によって対象のBとEの頂点の距離は算出されていないので、このままこの値を保持します。この時点ではBの頂点への最短距離は80、Eの頂点への最短距離は200となっています。
また、その最短距離になる直前のエッジの情報を格納します（今回はA-B間のエッジとA-E間のエッジ）。
次に[3]の計算として、対象をBの頂点に移動します。
Bの頂点に隣接しているのはA・C・D・Eの4つの頂点なのでそれぞれに対して計算を行います。
まずBからAの距離ですが、これは経路で戻る計算になってしまいます。もともとAからAへの距離は0としていたので、A → B → Aといくルートは距離が80 + 80 で160になります。この距離が0よりも大きいので距離やエッジの参照を更新しません。
同様にBからEへのルートに関しても距離が290となり、これはすでにAからEへ移動する場合の経路の距離の200よりも大きいので最短距離とエッジの参照を更新しません。
BからC及びBからDはまだ別ルートから距離が計算されていないので、新たに最短距離として採用・保持します。
[3]のステップでBの頂点の計算が終わると以下のようになります。
このように順番に対象の頂点をずらしていって、隣接する頂点への距離がまだ計算されていない、もしくは最短距離が短くなる場合の更新を繰り返します。更新された隣接する頂点を後々に対象とする頂点としてキューに追加していき計算をします。
Pythonでの実装で使うもの
- Python 3.8.5
Pythonでの実装
まずは必要なモジュールをimportしていきます。型アノテーションを利用するのでannotationsと、typingパッケージの各クラスを追加します。また、ダイクストラ法の計算で対象にしていく頂点の制御のために優先度付きキューを使う（使わなくても普通のキューでいけるような気もする）ため、heapqパッケージのものを読み込んでいます。
from __future__ import annotations
from typing import Tuple, List, Optional, Dict
from heapq import heappush, heappop
続いて頂点のための定数などを定義していきます。VertexStrは単純なstrの型エイリアスです。乱用するとクラスと見分けが付きづらいという弊害もあるかもしれませんが、「この引数は頂点の定数の文字列だよ」と分かりやすくするために便利なので今回は使っていきます。
VertexStr = str
class Vertex:
"""各頂点を表す文字列の定数を扱うクラス。
"""
A: VertexStr = 'A'
B: VertexStr = 'B'
C: VertexStr = 'C'
D: VertexStr = 'D'
E: VertexStr = 'E'
F: VertexStr = 'F'
G: VertexStr = 'G'
H: VertexStr = 'H'
I: VertexStr = 'I'
J: VertexStr = 'J'
K: VertexStr = 'K'
続いてエッジ用のクラスを定義していきます。（どの頂点からどの頂点へ繋ぐためのエッジなのかの判定用に）頂点情報やそのエッジにおける重み（今回は距離）を属性に保持します。
class Edge:
def __init__(
self, from_idx: int, to_idx: int,
from_vertex: VertexStr, to_vertex: VertexStr,
weight: float) -> None:
"""
エッジ単体を扱うクラス。
Parameters
----------
from_idx : int
接続元の頂点のインデックス。
to_idx : int
接続先の頂点のインデックス。
weight : float
エッジの重み。
"""
self.from_idx: int = from_idx
self.to_idx: int = to_idx
self.from_vertex: VertexStr = from_vertex
self.to_vertex: VertexStr = to_vertex
self.weight: float = weight
エッジの追加処理で、向きを反転させたもの追加で便利なため反転用のメソッドを追加しておきます（頂点A → 頂点Bのエッジから頂点B → 頂点Aのエッジを生成するなど）。
def reversed(self) -> Edge:
"""
頂点の接続元と接続先を反転させたエッジを取得する。
Returns
-------
reversed_edge : Edge
頂点の接続元と接続先を反転させたエッジ。
"""
reversed_edge = Edge(
from_idx=self.to_idx,
to_idx=self.from_idx,
from_vertex=self.from_vertex,
to_vertex=self.to_vertex,
weight=self.weight)
return reversed_edge
また、後々に経路の出力時などに便利なように、このクラスのインスタンスをprint関数などで出力した際の内容を調整しておきます。以下のように出力されるようになります。
from: A(weight: 80) -> to: B
def __str__(self) -> str:
"""
エッジの情報を文字列に変換する。
Returns
-------
edge_info_str : str
変換されたエッジ情報の文字列。
"""
edge_info_str: str = (
f'from: {self.from_vertex}'
f'(weight: {self.weight})'
f' -> to: {self.to_vertex}'
)
return edge_info_str
続いてグラフ用のクラスを定義していきます。引数のverticesには``A, B`, `C`...といったようにVertexクラスの定数の値のリストを後々指定します。
_edgesという属性に、頂点の数だけループを回して多次元のリストを作成しています。2次元目には対象の頂点に接続されている複数のエッジを格納します。まだこの時点ではエッジは空ですが、後々追加します。
class Graph:
def __init__(self, vertices: List[VertexStr]) -> None:
"""
グラフを扱うためのクラス。
Parameters
----------
vertices : list of str
頂点の文字列のリスト。
"""
self._vertices: List[VertexStr] = vertices
self._edges: List[List[Edge]] = []
for _ in vertices:
self._edges.append([])
いくつか計算で必要な各メソッドを追加していきます。まずは対象のインデックスの位置の頂点を取得するメソッドからです。
def vertex_at(self, index: int) -> VertexStr:
"""
指定されたインデックスの頂点の文字列を取得する。
Parameters
----------
index : int
対象のインデックス。
Returns
-------
vertex_str : str
対象のインデックス位置の頂点の文字列。
"""
return self._vertices[index]
逆に、頂点の文字列から該当するインデックスを取得するメソッドを追加します。
def index_of(self, vertex: VertexStr) -> int:
"""
対象の頂点のインテックスを取得する。
Parameters
----------
vertex : str
対象の頂点識別用の文字列。
Returns
-------
index : int
対象の頂点のインデックス。
"""
return self._vertices.index(vertex)
頂点がいくつあるのかのプロパティとしてのメソッドを追加します。
@property
def vertex_count(self):
"""
設定されている頂点数の属性値。
Returns
-------
vertex_count : int
設定されている頂点数。
"""
return len(self._vertices)
対象のインデックス位置の頂点に繋がっているエッジのリストを取得するメソッドを追加します。
def edges_at(self, vertex_index: int) -> List[Edge]:
"""
指定のインデックス位置の頂点に設定されているエッジの
リストを取得する。
Parameters
----------
vertex_index : int
対象の頂点位置のインデックス。
Returns
-------
edges : list of Edge
対象の頂点に設定されているエッジのリスト。
"""
return self._edges[vertex_index]
指定された頂点に隣接する頂点と、そのエッジの重みを格納したタプルのリストを取得する処理を追加します。特定の頂点で、最短距離を出す時に隣接している頂点を出す計算で使います。
def get_neighbor_vertices_and_weights_by_index(
self, vertex_index: int) -> List[Tuple[VertexStr, float]]:
"""
指定されたインデックスの頂点にエッジで繋がっている
頂点とそのエッジの重みの値のタプルのリストを取得する。
Parameters
----------
vertex_index : int
対象の頂点のインデックス。
Returns
-------
neighbor_vertices_and_weights : list of tuple
算出された頂点とそのエッジの重みのタプルを格納したリスト。
"""
neighbor_vertices_and_weights: List[Tuple[VertexStr, float]] = []
for edge in self.edges_at(vertex_index=vertex_index):
tuple_val = (
self.vertex_at(index=edge.to_idx),
edge.weight,
)
neighbor_vertices_and_weights.append(tuple_val)
return neighbor_vertices_and_weights
エッジをグラフに追加するメソッドを追加します。記述が少なくなるように、逆方向のエッジも追加されるようにします。たとえばA → Bの方向のエッジが追加されたら、B → Aの方向のエッジも追加されるようにします。反転したエッジを生成するにはEdgeクラスに追加したreversedメソッドを使います。
def add_edge(self, edge: Edge) -> None:
"""
グラフにエッジの追加を行う。
Notes
-----
反転させたエッジも接続先の頂点に対して追加される（エッジが
メソッド実行で合計で2件追加される）。
Parameters
----------
edge : Edge
追加対象のエッジ。
"""
self._edges[edge.from_idx].append(edge)
self._edges[edge.to_idx].append(edge.reversed())
続いて指定された2つの頂点の文字に応じてエッジが追加されるメソッドも追加します。これによって、「AとBの間にエッジを追加する」といった記述ができます。内部ではadd_edgeメソッドが呼ばれているので、逆方向のエッジも（反転させる形で）追加されます。
グラフのクラスの最後として、printなどした際に追加されている頂点とそれらの頂点に設定されている隣接頂点（とエッジ）の情報が出力されるようにしておきます。以下のように出力されるようになります。
グラフ情報:
対象の頂点 : A -> 隣接頂点データ : [('B', 80), ('E', 200)]
対象の頂点 : B -> 隣接頂点データ : [('A', 80), ('C', 92), ('D', 83), ('E', 210)]
...
def __str__(self) -> str:
"""
グラフ情報の文字列を返却する。
Returns
-------
graph_info : str
グラフ情報の文字列。
"""
graph_info: str = ''
for index in range(self.vertex_count):
neighbors_data = self.get_neighbor_vertices_and_weights_by_index(
vertex_index=index)
graph_info += (
f'対象の頂点 : {self.vertex_at(index=index)}'
f' -> 隣接頂点データ : {neighbors_data}\n'
)
return graph_info
続いてダイクストラ法による、スタートの頂点から特定の頂点への距離などを扱ったり、重み（距離）の計算用の処理を記述したクラスを追加します。
class DijkstraDistanceVertex:
def __init__(self, vertex_idx: int, distance: float) -> None:
"""
ダイクストラ法のための、特定の頂点のスタートの頂点からの距離（重み）
や他の頂点との比較制御のためのクラス。
Parameters
----------
vertex : str
対象の頂点識別用のインデックス。
distance : float
スタートの頂点からの距離。
"""
self.vertex_idx = vertex_idx
self.distance = distance
重みの比較用のメソッドを追加します。ダイクストラ法で、計算後に既に計算済みの頂点へのルートが短くなるのかの判定に使われます。
def __lt__(self, other: DijkstraDistanceVertex) -> bool:
"""
他の頂点の距離（重み）の小なりの比較結果の真偽値を取得する。
Parameters
----------
other : DijkstraDistanceVertex
比較対象の頂点。
Returns
-------
result : bool
Trueで小なりの条件を満たす場合。
"""
return self.distance < other.distance
def __eq__(self, other: DijkstraDistanceVertex) -> bool:
"""
他の頂点との距離（重み）が一致しているかどうかの真偽値を
取得する。
Parameters
----------
other : DijkstraDistanceVertex
比較対象の頂点。
Returns
-------
result : bool
Trueで一致の条件を満たす場合。
"""
return self.distance == other.distance
次は優先度付きのキューのクラスの準備です。各頂点への最短距離が更新される度に、キューにその頂点が追加されていきます。結局のところ全部に対して計算がされるので、優先度付きじゃなくても普通にキューでも良かった・・・？気がしないでもないです。
class PriorityQueue:
def __init__(self) -> None:
"""
優先度付きキューを扱うクラス。
"""
self._container: List[DijkstraDistanceVertex] = []
@property
def empty(self) -> bool:
"""
キューが空かどうかの真偽値の属性。
Returns
-------
result : bool
キューが空であればTrueが設定される。
"""
return not self._container
def push(self, item: DijkstraDistanceVertex) -> None:
"""
キューにダイクストラ法の特定頂点のスタートからの距離を扱う
インスタンスを追加する。
Parameters
----------
item : DijkstraDistanceVertex
追加対象のインスタンス。
"""
heappush(self._container, item)
def pop(self) -> DijkstraDistanceVertex:
"""
キューから優先度に応じたインスタンスを1件取り出す。
Returns
-------
item : DijkstraDistanceVertex
取り出されたインスタンス。
"""
return heappop(self._container)
もろもろのグラフの準備ができたのでダイクストラ法の計算を書いていきます。
def dijkstra(
graph: Graph,
root_vertex: VertexStr
) -> tuple[List[Optional[float]], Dict[int, Edge]]:
"""
ダイクストラ法を実施し、各頂点ごとの距離と各頂点までの最短ルートの
パスを算出する。
Parameters
----------
graph : Graph
対象のグラフ。
root_vertex : str
探索を開始する位置の頂点識別用の文字列。
Returns
-------
distances : list of float
各頂点の探索開始位置の頂点からの距離。
path_dict : dict
キーに対象の頂点のインデックス、値にはその頂点に到達する
のに最短となるルートの、直前のエッジを格納する。
"""
first_idx: int = graph.index_of(vertex=root_vertex)
distances: List[Optional[float]] = [
None for _ in range(graph.vertex_count)]
distances[first_idx] = 0
path_dict: Dict[int, Edge] = {}
priority_queue: PriorityQueue = PriorityQueue()
priority_queue.push(
item=DijkstraDistanceVertex(
vertex_idx=first_idx,
distance=0))
while not priority_queue.empty:
from_idx:int = priority_queue.pop().vertex_idx
from_vertex_distance: float = distances[from_idx]
for edge in graph.edges_at(vertex_index=from_idx):
# 対象のイテレーション前に既に対象の頂点へ設定されている
# 距離を取得する（別の経路などで設定されている値）。
to_distance: Optional[float] = distances[edge.to_idx]
# 今回の経路での距離を算出する。
current_route_distance: float = edge.weight + from_vertex_distance
# もし別ルートでの距離が既に設定されており、且つ今回の経路での
# 距離の方が短くならなければ更新処理をスキップする。
if (to_distance is not None
and to_distance <= current_route_distance):
continue
distances[edge.to_idx] = current_route_distance
path_dict[edge.to_idx] = edge
priority_queue.push(
item=DijkstraDistanceVertex(
vertex_idx=edge.to_idx,
distance=current_route_distance))
return distances, path_dict
引数のroot_vertexには，今回はAからJへの最短経路を出したいので後々Aを指定します。
while not priority_queue.empty:
といったように、探索対象の頂点がキューから無くなるまで処理をwhile文で継続します。
to_distance: Optional[float] = distances[edge.to_idx]
while文の中では、計算対象の頂点に対する距離を過去の値（別ルートで既に計算された値）を取得しています。最初はNoneを設定しているので、もし初めての頂点であればNoneとなります。
current_route_distance: float = edge.weight + from_vertex_distance
while文の現在の距離を計算しています。直前のエッジの重み（距離）と直前の頂点までの距離を合算しています。
if (to_distance is not None
and to_distance <= current_route_distance):
continue
もし他のルートで計算された距離が既にあり、且つ今回のイテレーションで計算した距離が短くならないようであれば更新などは不要なので処理をスキップします。
distances[edge.to_idx] = current_route_distance
path_dict[edge.to_idx] = edge
priority_queue.push(
item=DijkstraDistanceVertex(
vertex_idx=edge.to_idx,
distance=current_route_distance))
もし距離が短くなるとか、もしくは初めて計算する頂点であればその頂点に対する距離を更新し、その頂点へ至る最短距離の直前のエッジの情報も更新し、そしてその頂点を後々のイテレーションで計算するようにキューに追加します。
return distances, path_dict
返却値は各頂点への最短距離の情報を格納したリストと、各頂点への最短距離になるルートでの直前のエッジを格納した辞書となります。
続いて、算出された各頂点の最短経路の直前のエッジを格納した辞書から、スタートの頂点から任意の最終頂点までの最短経路を取得するための関数を用意します。
計算方法で前述したように、最終頂点（今回はJ）から順番に最短距離となる直前のノードを辿っていき、そのエッジをリストへ追加していきます。スタートの頂点に達したらループを停止します。また、返却前にスタートの頂点 → 最終頂点の順になるようにreveseメソッドで反転させておきます。
def to_route_path_from_path_dict(
start_vertex_idx: int,
last_vertex_idx: int,
path_dict: Dict[int, Edge]) -> RoutePath:
"""
そのパスへ至る際に最短距離となる直前のエッジを格納した辞書を使用して、
指定された頂点への最短距離となる
Parameters
----------
start_vertex_idx : int
求めたい経路の開始地点となる頂点の
last_vertex_idx : int
求めたい経路の最終地点となる頂点のインデックス。
path_dict : dict
キーに対象の頂点のインデックス、値にその頂点へ至る最短経路の
直前のエッジを格納した辞書。
"""
route_path: RoutePath = []
current_edge: Edge = path_dict[last_vertex_idx]
route_path.append(current_edge)
while current_edge.from_idx != start_vertex_idx:
current_edge = path_dict[current_edge.from_idx]
route_path.append(current_edge)
route_path.reverse()
return route_path
最後に、用意したものを使ってグラフのインスタンス化やノードの追加などをやって、計算と計算結果を出力して完成です。
if __name__ == '__main__':
graph = Graph(
vertices=[
Vertex.A,
Vertex.B,
Vertex.C,
Vertex.D,
Vertex.E,
Vertex.F,
Vertex.G,
Vertex.H,
Vertex.I,
Vertex.J,
Vertex.K,
])
graph.add_edge_by_vertices(
from_vertex=Vertex.A,
to_vertex=Vertex.B,
weight=80)
graph.add_edge_by_vertices(
from_vertex=Vertex.A,
to_vertex=Vertex.E,
weight=200)
graph.add_edge_by_vertices(
from_vertex=Vertex.B,
to_vertex=Vertex.C,
weight=92)
graph.add_edge_by_vertices(
from_vertex=Vertex.B,
to_vertex=Vertex.D,
weight=83)
graph.add_edge_by_vertices(
from_vertex=Vertex.B,
to_vertex=Vertex.E,
weight=210)
graph.add_edge_by_vertices(
from_vertex=Vertex.C,
to_vertex=Vertex.D,
weight=43)
graph.add_edge_by_vertices(
from_vertex=Vertex.C,
to_vertex=Vertex.E,
weight=93)
graph.add_edge_by_vertices(
from_vertex=Vertex.C,
to_vertex=Vertex.F,
weight=66)
graph.add_edge_by_vertices(
from_vertex=Vertex.D,
to_vertex=Vertex.G,
weight=95)
graph.add_edge_by_vertices(
from_vertex=Vertex.D,
to_vertex=Vertex.H,
weight=123)
graph.add_edge_by_vertices(
from_vertex=Vertex.E,
to_vertex=Vertex.F,
weight=81)
graph.add_edge_by_vertices(
from_vertex=Vertex.F,
to_vertex=Vertex.G,
weight=46)
graph.add_edge_by_vertices(
from_vertex=Vertex.F,
to_vertex=Vertex.K,
weight=100)
graph.add_edge_by_vertices(
from_vertex=Vertex.G,
to_vertex=Vertex.H,
weight=141)
graph.add_edge_by_vertices(
from_vertex=Vertex.G,
to_vertex=Vertex.I,
weight=53)
graph.add_edge_by_vertices(
from_vertex=Vertex.G,
to_vertex=Vertex.K,
weight=112)
graph.add_edge_by_vertices(
from_vertex=Vertex.H,
to_vertex=Vertex.I,
weight=86)
graph.add_edge_by_vertices(
from_vertex=Vertex.I,
to_vertex=Vertex.J,
weight=95)
graph.add_edge_by_vertices(
from_vertex=Vertex.J,
to_vertex=Vertex.K,
weight=92)
print('-' * 20)
print('グラフ情報:')
print(graph)
print('-' * 20)
distances, path_dict = dijkstra(
graph=graph,
root_vertex=Vertex.A)
print('算出された頂点Aから各頂点への最短距離情報:')
for index, distance in enumerate(distances):
vertex: VertexStr = graph.vertex_at(index=index)
print('頂点 :', vertex, '距離 :', distance)
print('-' * 20)
start_vertex_idx = graph.index_of(vertex=Vertex.A)
last_vertex_idx = graph.index_of(vertex=Vertex.J)
route_path: RoutePath = to_route_path_from_path_dict(
start_vertex_idx=start_vertex_idx,
last_vertex_idx=last_vertex_idx,
path_dict=path_dict)
print('頂点Aから頂点Jまでの最短経路:')
for edge in route_path:
print(edge)
グラフ情報は以下のように出力されます。
グラフ情報:
対象の頂点 : A -> 隣接頂点データ : [('B', 80), ('E', 200)]
対象の頂点 : B -> 隣接頂点データ : [('A', 80), ('C', 92), ('D', 83), ('E', 210)]
対象の頂点 : C -> 隣接頂点データ : [('B', 92), ('D', 43), ('E', 93), ('F', 66)]
対象の頂点 : D -> 隣接頂点データ : [('B', 83), ('C', 43), ('G', 95), ('H', 123)]
対象の頂点 : E -> 隣接頂点データ : [('A', 200), ('B', 210), ('C', 93), ('F', 81)]
対象の頂点 : F -> 隣接頂点データ : [('C', 66), ('E', 81), ('G', 46), ('K', 100)]
対象の頂点 : G -> 隣接頂点データ : [('D', 95), ('F', 46), ('H', 141), ('I', 53), ('K', 112)]
対象の頂点 : H -> 隣接頂点データ : [('D', 123), ('G', 141), ('I', 86)]
対象の頂点 : I -> 隣接頂点データ : [('G', 53), ('H', 86), ('J', 95)]
対象の頂点 : J -> 隣接頂点データ : [('I', 95), ('K', 92)]
対象の頂点 : K -> 隣接頂点データ : [('F', 100), ('G', 112), ('J', 92)]
各頂点への最短距離は以下のように出力されます。
算出された頂点Aから各頂点への最短距離情報:
頂点 : A 距離 : 0
頂点 : B 距離 : 80
頂点 : C 距離 : 172
頂点 : D 距離 : 163
頂点 : E 距離 : 200
頂点 : F 距離 : 238
頂点 : G 距離 : 258
頂点 : H 距離 : 286
頂点 : I 距離 : 311
頂点 : J 距離 : 406
頂点 : K 距離 : 338
そして最短経路はA → B → D → G → I → Jと算出されました。
頂点Aから頂点Jまでの最短経路:
from: A(weight: 80) -> to: B
from: B(weight: 83) -> to: D
from: D(weight: 95) -> to: G
from: G(weight: 53) -> to: I
from: I(weight: 95) -> to: J
グラフの画像を見てみると、確かに合っていそうです。
余談
元々デザイン方面の学校卒なので、コンピューターサイエンス方面で知識的に雑な点などへの強めのマサカリはご容赦くださいmm
コード全体
from __future__ import annotations
from typing import Tuple, List, Optional, Dict
from heapq import heappush, heappop
VertexStr = str
class Vertex:
"""各頂点を表す文字列の定数を扱うクラス。
"""
A: VertexStr = 'A'
B: VertexStr = 'B'
C: VertexStr = 'C'
D: VertexStr = 'D'
E: VertexStr = 'E'
F: VertexStr = 'F'
G: VertexStr = 'G'
H: VertexStr = 'H'
I: VertexStr = 'I'
J: VertexStr = 'J'
K: VertexStr = 'K'
class Edge:
def __init__(
self, from_idx: int, to_idx: int,
from_vertex: VertexStr, to_vertex: VertexStr,
weight: float) -> None:
"""
エッジ単体を扱うクラス。
Parameters
----------
from_idx : int
接続元の頂点のインデックス。
to_idx : int
接続先の頂点のインデックス。
weight : float
エッジの重み。
"""
self.from_idx: int = from_idx
self.to_idx: int = to_idx
self.from_vertex: VertexStr = from_vertex
self.to_vertex: VertexStr = to_vertex
self.weight: float = weight
def reversed(self) -> Edge:
"""
頂点の接続元と接続先を反転させたエッジを取得する。
Returns
-------
reversed_edge : Edge
頂点の接続元と接続先を反転させたエッジ。
"""
reversed_edge = Edge(
from_idx=self.to_idx,
to_idx=self.from_idx,
from_vertex=self.from_vertex,
to_vertex=self.to_vertex,
weight=self.weight)
return reversed_edge
def __str__(self) -> str:
"""
エッジの情報を文字列に変換する。
Returns
-------
edge_info_str : str
変換されたエッジ情報の文字列。
"""
edge_info_str: str = (
f'from: {self.from_vertex}'
f'(weight: {self.weight})'
f' -> to: {self.to_vertex}'
)
return edge_info_str
class Graph:
def __init__(self, vertices: List[VertexStr]) -> None:
"""
グラフを扱うためのクラス。
Parameters
----------
vertices : list of str
頂点の文字列のリスト。
"""
self._vertices: List[VertexStr] = vertices
self._edges: List[List[Edge]] = []
for _ in vertices:
self._edges.append([])
def vertex_at(self, index: int) -> VertexStr:
"""
指定されたインデックスの頂点の文字列を取得する。
Parameters
----------
index : int
対象のインデックス。
Returns
-------
vertex_str : str
対象のインデックス位置の頂点の文字列。
"""
return self._vertices[index]
def index_of(self, vertex: VertexStr) -> int:
"""
対象の頂点のインテックスを取得する。
Parameters
----------
vertex : str
対象の頂点識別用の文字列。
Returns
-------
index : int
対象の頂点のインデックス。
"""
return self._vertices.index(vertex)
@property
def vertex_count(self):
"""
設定されている頂点数の属性値。
Returns
-------
vertex_count : int
設定されている頂点数。
"""
return len(self._vertices)
def edges_at(self, vertex_index: int) -> List[Edge]:
"""
指定のインデックス位置の頂点に設定されているエッジの
リストを取得する。
Parameters
----------
vertex_index : int
対象の頂点位置のインデックス。
Returns
-------
edges : list of Edge
対象の頂点に設定されているエッジのリスト。
"""
return self._edges[vertex_index]
def get_neighbor_vertices_and_weights_by_index(
self, vertex_index: int) -> List[Tuple[VertexStr, float]]:
"""
指定されたインデックスの頂点にエッジで繋がっている
頂点とそのエッジの重みの値のタプルのリストを取得する。
Parameters
----------
vertex_index : int
対象の頂点のインデックス。
Returns
-------
neighbor_vertices_and_weights : list of tuple
算出された頂点とそのエッジの重みのタプルを格納したリスト。
"""
neighbor_vertices_and_weights: List[Tuple[VertexStr, float]] = []
for edge in self.edges_at(vertex_index=vertex_index):
tuple_val = (
self.vertex_at(index=edge.to_idx),
edge.weight,
)
neighbor_vertices_and_weights.append(tuple_val)
return neighbor_vertices_and_weights
def add_edge(self, edge: Edge) -> None:
"""
グラフにエッジの追加を行う。
Notes
-----
反転させたエッジも接続先の頂点に対して追加される（エッジが
メソッド実行で合計で2件追加される）。
Parameters
----------
edge : Edge
追加対象のエッジ。
"""
self._edges[edge.from_idx].append(edge)
self._edges[edge.to_idx].append(edge.reversed())
def add_edge_by_vertices(
self, from_vertex: VertexStr,
to_vertex: VertexStr,
weight: float) -> None:
"""
指定された2つの頂点間のエッジの追加を行う。
Parameters
----------
from_vertex : str
接続元の頂点の指定。
to_vertex : str
接続先の頂点の指定。
weight : float
エッジの重みの値。
"""
from_idx = self._vertices.index(from_vertex)
to_idx = self._vertices.index(to_vertex)
edge = Edge(
from_idx=from_idx,
to_idx=to_idx,
from_vertex=from_vertex,
to_vertex=to_vertex,
weight=weight)
self.add_edge(edge=edge)
def __str__(self) -> str:
"""
グラフ情報の文字列を返却する。
Returns
-------
graph_info : str
グラフ情報の文字列。
"""
graph_info: str = ''
for index in range(self.vertex_count):
neighbors_data = self.get_neighbor_vertices_and_weights_by_index(
vertex_index=index)
graph_info += (
f'対象の頂点 : {self.vertex_at(index=index)}'
f' -> 隣接頂点データ : {neighbors_data}\n'
)
return graph_info
class DijkstraDistanceVertex:
def __init__(self, vertex_idx: int, distance: float) -> None:
"""
ダイクストラ法のための、特定の頂点のスタートの頂点からの距離（重み）
や他の頂点との比較制御のためのクラス。
Parameters
----------
vertex : str
対象の頂点識別用のインデックス。
distance : float
スタートの頂点からの距離。
"""
self.vertex_idx = vertex_idx
self.distance = distance
def __lt__(self, other: DijkstraDistanceVertex) -> bool:
"""
他の頂点の距離（重み）の小なりの比較結果の真偽値を取得する。
Parameters
----------
other : DijkstraDistanceVertex
比較対象の頂点。
Returns
-------
result : bool
Trueで小なりの条件を満たす場合。
"""
return self.distance < other.distance
def __eq__(self, other: DijkstraDistanceVertex) -> bool:
"""
他の頂点との距離（重み）が一致しているかどうかの真偽値を
取得する。
Parameters
----------
other : DijkstraDistanceVertex
比較対象の頂点。
Returns
-------
result : bool
Trueで一致の条件を満たす場合。
"""
return self.distance == other.distance
class PriorityQueue:
def __init__(self) -> None:
"""
優先度付きキューを扱うクラス。
"""
self._container: List[DijkstraDistanceVertex] = []
@property
def empty(self) -> bool:
"""
キューが空かどうかの真偽値の属性。
Returns
-------
result : bool
キューが空であればTrueが設定される。
"""
return not self._container
def push(self, item: DijkstraDistanceVertex) -> None:
"""
キューにダイクストラ法の特定頂点のスタートからの距離を扱う
インスタンスを追加する。
Parameters
----------
item : DijkstraDistanceVertex
追加対象のインスタンス。
"""
heappush(self._container, item)
def pop(self) -> DijkstraDistanceVertex:
"""
キューから優先度に応じたインスタンスを1件取り出す。
Returns
-------
item : DijkstraDistanceVertex
取り出されたインスタンス。
"""
return heappop(self._container)
def dijkstra(
graph: Graph,
root_vertex: VertexStr
) -> tuple[List[Optional[float]], Dict[int, Edge]]:
"""
ダイクストラ法を実施し、各頂点ごとの距離と各頂点までの最短ルートの
パスを算出する。
Parameters
----------
graph : Graph
対象のグラフ。
root_vertex : str
探索を開始する位置の頂点識別用の文字列。
Returns
-------
distances : list of float
各頂点の探索開始位置の頂点からの距離。
path_dict : dict
キーに対象の頂点のインデックス、値にはその頂点に到達する
のに最短となるルートの、直前のエッジを格納する。
"""
first_idx: int = graph.index_of(vertex=root_vertex)
distances: List[Optional[float]] = [
None for _ in range(graph.vertex_count)]
distances[first_idx] = 0
path_dict: Dict[int, Edge] = {}
priority_queue: PriorityQueue = PriorityQueue()
priority_queue.push(
item=DijkstraDistanceVertex(
vertex_idx=first_idx,
distance=0))
while not priority_queue.empty:
from_idx:int = priority_queue.pop().vertex_idx
from_vertex_distance: float = distances[from_idx]
for edge in graph.edges_at(vertex_index=from_idx):
# 対象のイテレーション前に既に対象の頂点へ設定されている
# 距離を取得する（別の経路などで設定されている値）。
to_distance: Optional[float] = distances[edge.to_idx]
# 今回の経路での距離を算出する。
current_route_distance: float = edge.weight + from_vertex_distance
# もし別ルートでの距離が既に設定されており、且つ今回の経路での
# 距離の方が短くならなければ更新処理をスキップする。
if (to_distance is not None
and to_distance <= current_route_distance):
continue
distances[edge.to_idx] = current_route_distance
path_dict[edge.to_idx] = edge
priority_queue.push(
item=DijkstraDistanceVertex(
vertex_idx=edge.to_idx,
distance=current_route_distance))
return distances, path_dict
RoutePath = List[Edge]
def to_route_path_from_path_dict(
start_vertex_idx: int,
last_vertex_idx: int,
path_dict: Dict[int, Edge]) -> RoutePath:
"""
そのパスへ至る際に最短距離となる直前のエッジを格納した辞書を使用して、
指定された頂点への最短距離となる
Parameters
----------
start_vertex_idx : int
求めたい経路の開始地点となる頂点の
last_vertex_idx : int
求めたい経路の最終地点となる頂点のインデックス。
path_dict : dict
キーに対象の頂点のインデックス、値にその頂点へ至る最短経路の
直前のエッジを格納した辞書。
"""
route_path: RoutePath = []
current_edge: Edge = path_dict[last_vertex_idx]
route_path.append(current_edge)
while current_edge.from_idx != start_vertex_idx:
current_edge = path_dict[current_edge.from_idx]
route_path.append(current_edge)
route_path.reverse()
return route_path
if __name__ == '__main__':
graph = Graph(
vertices=[
Vertex.A,
Vertex.B,
Vertex.C,
Vertex.D,
Vertex.E,
Vertex.F,
Vertex.G,
Vertex.H,
Vertex.I,
Vertex.J,
Vertex.K,
])
graph.add_edge_by_vertices(
from_vertex=Vertex.A,
to_vertex=Vertex.B,
weight=80)
graph.add_edge_by_vertices(
from_vertex=Vertex.A,
to_vertex=Vertex.E,
weight=200)
graph.add_edge_by_vertices(
from_vertex=Vertex.B,
to_vertex=Vertex.C,
weight=92)
graph.add_edge_by_vertices(
from_vertex=Vertex.B,
to_vertex=Vertex.D,
weight=83)
graph.add_edge_by_vertices(
from_vertex=Vertex.B,
to_vertex=Vertex.E,
weight=210)
graph.add_edge_by_vertices(
from_vertex=Vertex.C,
to_vertex=Vertex.D,
weight=43)
graph.add_edge_by_vertices(
from_vertex=Vertex.C,
to_vertex=Vertex.E,
weight=93)
graph.add_edge_by_vertices(
from_vertex=Vertex.C,
to_vertex=Vertex.F,
weight=66)
graph.add_edge_by_vertices(
from_vertex=Vertex.D,
to_vertex=Vertex.G,
weight=95)
graph.add_edge_by_vertices(
from_vertex=Vertex.D,
to_vertex=Vertex.H,
weight=123)
graph.add_edge_by_vertices(
from_vertex=Vertex.E,
to_vertex=Vertex.F,
weight=81)
graph.add_edge_by_vertices(
from_vertex=Vertex.F,
to_vertex=Vertex.G,
weight=46)
graph.add_edge_by_vertices(
from_vertex=Vertex.F,
to_vertex=Vertex.K,
weight=100)
graph.add_edge_by_vertices(
from_vertex=Vertex.G,
to_vertex=Vertex.H,
weight=141)
graph.add_edge_by_vertices(
from_vertex=Vertex.G,
to_vertex=Vertex.I,
weight=53)
graph.add_edge_by_vertices(
from_vertex=Vertex.G,
to_vertex=Vertex.K,
weight=112)
graph.add_edge_by_vertices(
from_vertex=Vertex.H,
to_vertex=Vertex.I,
weight=86)
graph.add_edge_by_vertices(
from_vertex=Vertex.I,
to_vertex=Vertex.J,
weight=95)
graph.add_edge_by_vertices(
from_vertex=Vertex.J,
to_vertex=Vertex.K,
weight=92)
print('-' * 20)
print('グラフ情報:')
print(graph)
print('-' * 20)
distances, path_dict = dijkstra(
graph=graph,
root_vertex=Vertex.A)
print('算出された頂点Aから各頂点への最短距離情報:')
for index, distance in enumerate(distances):
vertex: VertexStr = graph.vertex_at(index=index)
print('頂点 :', vertex, '距離 :', distance)
print('-' * 20)
start_vertex_idx = graph.index_of(vertex=Vertex.A)
last_vertex_idx = graph.index_of(vertex=Vertex.J)
route_path: RoutePath = to_route_path_from_path_dict(
start_vertex_idx=start_vertex_idx,
last_vertex_idx=last_vertex_idx,
path_dict=path_dict)
print('頂点Aから頂点Jまでの最短経路:')
for edge in route_path:
print(edge)