Python의 다익스트라 알고리즘
Dijkstra의 알고리즘은 정점이 소스 정점에서 도달할 수 있는 경우 가중치 그래프에 존재하는 다른 가능한 정점까지 소스 정점에서 가능한 최단 거리를 찾는 데 사용할 수 있는 욕심 많은 알고리즘으로 정의할 수 있습니다.
이 튜토리얼에서는 Python에서 최단 경로를 찾기 위한 Dijkstra 알고리즘을 구현하는 방법에 대해 설명합니다.
위에서 언급했듯이 Dijkstra의 알고리즘은 탐욕적입니다. 탐욕스러운 알고리즘은 주어진 문제에 대한 개별 솔루션을 구축하고 가장 유익한 옵션을 선택하는 데 중점을 둔 알고리즘 패러다임으로 정의할 수 있습니다.
Dijkstra의 알고리즘이 작동하는 방식은 다음과 같습니다.
- 두 개의 방문하지 않은 정점이 주어지면 소스에서 가장 가까운 거리의 정점을 선택하여 방문합니다.
- 각 이웃에 대한 거리가 업데이트됩니다. 방문한 정점에 대해서도 동일한 작업이 수행되며, 이 정점은 현재 거리가 이들 사이의 주어진 가장자리의 합과 가중치보다 더 큽니다.
- 방문하지 않은 정점이 없을 때까지 1단계와 2단계를 반복해야 합니다.
Dijkstra의 알고리즘은 소스를 트리의 루트로 사용하는 SPT(최단 경로 트리) 생성이 필요하기 때문에 또 다른 Greedy 알고리즘인 Prim의 최소 스패닝 트리 알고리즘과 유사합니다.
다음 코드는 Python에서 최단 경로를 찾기 위해 Dijkstra 알고리즘을 사용합니다.
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
Dijkstra의 알고리즘은 깊이 우선 탐색 알고리즘과 매우 유사하지만 두 알고리즘 모두 동일한 목적으로 정확하게 존재하지는 않습니다.
Depth First Search와 Dijkstra의 알고리즘 간의 유일한 중요한 차이점은 DFS(Depth First Search) 알고리즘이 스택 기술을 사용하기 때문에 전자가 후자보다 느리게 작동한다는 것입니다. 반면에 Dijkstra의 알고리즘은 비교적 느린 힙 기술을 사용합니다.
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