티스토리 뷰
다익스트라 알고리즘은 하나의 정점에서 다른 정점으로 갈 때, 최단 경로를 알려주는 알고리즘이다.
여러개의 정점이 존재하는 그래프에서, 간선에 다음 노드로 가는 거리가 표시된다.
그 이후, 각 상황마다 갈 수 있는 짧은 경로를 선택한 뒤, 전에 있던 경로와 비교 갱신하여 최단 거리를 찾는다.
정확한 순서는 다음과 같다.
1. 출발 노드 설정
2. 출발 노드를 기준으로 각 노드의 최소 비용을 저장(위에서는 P와 U. 나머지는 inf 처리하는데 그냥 충분히 높은 값을 주면 된다.)
3. 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택(여기서는 P)
4. 해당 노드를 거쳐서 특정한 노드로 가는 경우를 고려하여 최소 비용을 갱신(즉, P에서는 X,Q로 갈 수 있는데 X로 가는 방식이 3+1과 2+4가 있므으로 4로 갱신)
5. 위 과정에서 3~4번을 반복
현재 상황에서 최선의 노드를 찾기 때문에, 그리드 알고리즘으로도 분류된다.
말로만 해서 이해가 되지 않는다면, 영상을 한 번 보고 학습하는 걸 추천한다.
https://www.youtube.com/watch?v=611B-9zk2o4
실전 코드를 짜는 법
영상에서는 C로 표시했지만, 필자는 파이썬으로 바꾸어 코드를 짜볼 것이다.
마침 다익스트라 문제를 풀어야 하기에, 다익스트라 그래프의 예시를 들 것이다.
num = 5
inf = 100000000;
li = [[inf,10,inf,inf,inf],
[10,inf,10,inf,inf],
[inf,10,inf,10,inf],
[inf,inf,10,inf,10],
[inf,inf,inf,10,inf]]
visited =[False] * 5 #방문한 노드
distance =[False] * 5 #최단 거리일단 간단하게 그래프를 만들어보았다.
간선의 연결 정보는 1-2, 2-3,3-4,4-5 이고, 당연하게도 대각선은 전부 inf 처리이다.
이 상황에서 방문 노드 여부와, 거리 저장의 리스트를 만들어준다. 당연하게도 개수는 간선의 양(5)과 동일하게 해준다.
이 상태에서 가장 최소 거리를 가지는 정점을 반환해야 하는 함수를 짜준다.
def get_small_distance():
min = inf
index =0
for i in range(num):
if not visited[i] and (distance[i] < min): #방문하지 않았고, 최소값보다 작다면
min = distance[i] #그 값으로 최소값을 갱신
index = i #그 위치를 기억
return index #최소거리를 가진 인덱스를 반환한다.
위의 유튜브에서 나오는 알고리즘을 파이썬으로 바꾸면 이렇게 된다.
가장 효율적인 방법은 아니지만 가장 쉬운 구현 방법이다.
다음으로는 다익스트라다.
모든 정점으로 가는 가장 최소 비용을 구해주는 함수이다.
def dijkstra(start):
for i in range(num):
distance[i] = li[start][i] #시작점에서 모든 곳까지 가는 비용을 담는다.
visited[start] = True #해당 노드를 방문 처리
for i in range(num-2): #현재 방문하지 않은 노드들 중에서
current = get_small_distance() #최소 비용을 가지는 인덱스를 가져온다.
visited[current] =True #그 노드를 방문 처리
for j in range(num): #현재 선택한 노드에 인접한 모든 노드들을 하나씩 확인 해보면서
if not visited[j]: #그 노드를 방문하지 않았다면
if(distance[current]+li[current][j]) < distance[j]: #현재 보고 있는 그 노드(current) 까지의 최소 비용에서
distance[j]= distance[current]+li[current][j] #현재 그 노드에서 j 노드까지 가는 값을 더한 값이
#현재 그 노드로 가는 최소 비용보다 작다면 갱신
주석을 주렁주렁 달아놨지만, 사실 언어만 바꿨을 뿐 유튜브 영상을 그대로 옮긴 것이므로 보면서 하면 된다.
여기까지 이해가 되었다면, 그냥 실행하면 된다.
dijkstra(0)
for i in range(5):
print(distance[i])
#실행 결과
100000000
10
20
30
40
여기서 inf 값이 나오는 건, 당연하게도 1->1 간선은 없기 때문이다.
각각의 거리는 1 노드에서 해당 노드까지 가는 걸 상정한다.
뭔가 밥 아저씨의 참 쉽죠 같은 느낌이지만, 한번만 이해하고 알고 있으면 진짜 편한 알고리즘이다.
위 코드에서 이해가 되지 않는 부분이 있을 수 있는데, 아마 이 부분일 거라 생각한다.
for j in range(num): #현재 선택한 노드에 인접한 모든 노드들을 하나씩 확인 해보면서
if not visited[j]: #그 노드를 방문하지 않았다면
if(distance[current]+li[current][j]) < distance[j]: #현재 보고 있는 그 노드(current) 까지의 최소 비용에서
distance[j]= distance[current]+li[current][j] #현재 그 노드에서 j 노드까지 가는 값을 더한 값이
#현재 그 노드로 가는 최소 비용보다 작다면 갱신
위 코드에서 get_small_distance()를 통해서, 현재 최소 거리를 가지고 있는 노드를 current에 불러왔다.
그렇다면 그 노드에서 다음 노드로 가야 하는데, 다음 노드를 돌아가면서 그 노드가 방문되지 않았는지를 찾는다
(위에서 current를 구했을 때 해당 노드를 방문 처리 해주는 건 이 때문이다.)
만약 방문되지 않았다면, 비교한다. 현재 노드까지 온 값(distance[current]와 ,li에 있는 current에서 다음 노드인 j까지 가는 값을 더한 값이 , distance[j]. 즉, 현재 그 노드로 가는 최소 비용보다 작다면, 갱신해주는 것이다.
영상에서 정말 잘 설명해주고 있으니 모르겠으면 영상을 보는 게 제일 좋다.
선형 탐색으로 찾는 방법이라 시간복잡도가 O(n^2)이라 좋은 방법은 아니지만, 일단 이해하기엔 쉽다.
만약 고수라면, heapq을 이용한 구조인 코드도 다음과 같이 사용할 수 있다.
import heapq
import sys
input = sys.stdin.readline
INF = int(1e9) #무한을 의미하는 값으로 10억
#노드의 개수, 간선의 개수를 입력받기
n,m = map(int, input().split())
#시작 노드 번호를 입력받기
start = int(input())
#각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트 만들기
graph = [[] for i in range(n+1)]
#최단 거리 테이블을 무한으로 초기화
distance = [INF]*(n+1)
#모든 간선 정보를 입력받기
for _ in range(m):
a,b,c = map(int, input().split())
#a번 노드에서 b번 노드로 가는 비용이 c
graph[a].append((b,c))
def dijkstra(start):
q=[]
#시작 노드로 가기 위한 최단 경로는 0으로 설정하여 큐에 삽입
heapq.heappush(q, (0, start))
distance[start]=0
#q가 비어있지 않다면
while q:
#가장 최단 거리인 노드에 대한 정보 꺼내기
dist, now = heapq.heappop(q)
#현재 노드가 이미 처리됐다면 skip
if distance[now] < dist:
continue
#현재 노드와 연결된 다른 인접한 노드 확인
for i in graph[now]:
cost = dist + i[1]
#현재 노드를 거치면 이동 거리가 더 짧은 경우
if cost < distance[i[0]]:
distance[i[0]] = cost
heapq.heappush(q, (cost, i[0]))
#다익스트라 알고리즘 실행
dijkstra(start)
#모든 노드로 가기 위한 최단 거리 출력
for i in range(1, n+1):
#도달할 수 없는 경우, 무한 출력
if distance[i]==INF:
print("INF")
else:
print(distance[i])