Python でのダイクストラのアルゴリズム
ダイクストラのアルゴリズムは、頂点がソース頂点から到達可能である場合に、ソース頂点から加重グラフに存在する他の可能な頂点までの可能な最短距離を見つけるために利用できる欲張りアルゴリズムとして定義できます。
このチュートリアルでは、Python で最短パスを見つけるためのダイクストラのアルゴリズムを実装する方法について説明します。
上記のように、ダイクストラのアルゴリズムは欲張りです。欲張りアルゴリズムは、与えられた問題に対するピースごとのソリューションを構築し、次に最も有益なオプションを選択することに焦点を当てたアルゴリズムパラダイムとして定義できます。
ダイクストラのアルゴリズムの仕組みは次のとおりです。
- 訪問されていない頂点がいくつかある場合、ソースからの距離が最も短い頂点を選択して訪問します。
- 次に、各隣接距離の距離が更新されます。訪問した頂点についても同じことが行われます。頂点の現在の距離は、それらの間の指定されたエッジの合計と重みよりも大きくなります。
- 未訪問の頂点がなくなるまで、手順 1 と 2 を繰り返す必要があります。
ダイクストラのアルゴリズムは、別の欲張りアルゴリズムであるプリムの最小スパニングツリーアルゴリズムに似ています。どちらも、ソースをツリーのルートとして、SPT（最短パスツリー）を生成する必要があるためです。
次のコードは、Python で最短パスを見つけるためにダイクストラのアルゴリズムを使用しています。
import sys
class Graph:
def __init__(self, vertx):
self.V = vertx
self.graph = [[0 for column in range(vertx)] for row in range(vertx)]
def pSol(self, dist):
print("Distance of vertex from source")
for node in range(self.V):
print(node, "t", dist[node])
def minDistance(self, dist, sptSet):
min = sys.maxsize
for v in range(self.V):
if dist[v] < min and sptSet[v] == False:
min = dist[v]
min_index = v
return min_index
def dijk(self, source):
dist = [sys.maxsize] * self.V
dist[source] = 0
sptSet = [False] * self.V
for cout in range(self.V):
u = self.minDistance(dist, sptSet)
sptSet[u] = True
for v in range(self.V):
if (
self.graph[u][v] > 0
and sptSet[v] == False
and dist[v] > dist[u] + self.graph[u][v]
):
dist[v] = dist[u] + self.graph[u][v]
self.pSol(dist)
f = Graph(9)
f.graph = [
[0, 4, 0, 0, 0, 0, 0, 8, 0],
[4, 0, 8, 0, 0, 0, 0, 11, 0],
[0, 8, 0, 7, 0, 4, 0, 0, 2],
[0, 0, 7, 0, 9, 14, 0, 0, 0],
[0, 0, 0, 9, 0, 10, 0, 0, 0],
[0, 0, 4, 14, 10, 0, 2, 0, 0],
[0, 0, 0, 0, 0, 2, 0, 1, 6],
[8, 11, 0, 0, 0, 0, 1, 0, 7],
[0, 0, 2, 0, 0, 0, 6, 7, 0],
]
f.dijk(0)
上記のコードは、次の出力を提供します。
Distance of vertex from source
0 t 0
1 t 4
2 t 12
3 t 19
4 t 21
5 t 11
6 t 9
7 t 8
8 t 14
ダイクストラのアルゴリズムは深さ優先探索アルゴリズムと非常に似ていますが、これらのアルゴリズムの両方が同じ目的のために正確に存在するわけではありません。
深さ優先探索とダイクストラのアルゴリズムの唯一の重要な違いは、深さ優先探索（DFS）アルゴリズムがスタック手法を使用するため、前者の方が後者よりも動作が遅いことです。一方、ダイクストラのアルゴリズムは、比較的遅いヒープ手法を使用します。
Vaibhhav is an IT professional who has a strong-hold in Python programming and various projects under his belt. He has an eagerness to discover new things and is a quick learner.
LinkedIn