최단 경로 알고리즘 - 다익스트라 - 2021/04/02

최단 경로 알고리즘

 

최단 경로 알고리즘이란

 

1. 한 지점에서 다른 한 지점으로 갈 때

2. 한 지점에서 다른 모든 지점으로 갈 때

3. 모든 지점에서 다른 모든 지점까지 갈 때

 

를 구하는 알고리즘이다.

 

최단 경로 알고리즘에는 다익스트라 알고리즘, 플로이드-워셜 알고리즘이 있는데 이번 글은 다익스트라 알고리즘에 관한 내용이다.

 

다익스트라 알고리즘

 

다익스트라 알고리즘은 매 상황에서 가장 비용이 적은 노드를 선택한다는 점에서 그리디 알고리즘으로 분류될 수 있다.

 

1. 출발노드를 설정한다

2. 최단거리 테이블을 초기화한다. -> 다른노드는 무한, 자기자신은 0

3. 방문하지 않은 노드 중 가장 짧은 노드 선택

4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산한다.

 

코드로 살펴보면

 

import heapq
# 우선순위 큐를 사용하기 때문에 heapq를 import한다.
INF=int(1e9)
n,m=map(int,input().split())
6 11
start=int(input())
1
graph=[[]for i in range(n+1)]
distance=[INF]*(n+1)
for i in range(m):
    a,b,c=map(int,input().split())
    graph[a].append((b,c))
    
1 2 2
1 3 5
1 4 1
2 3 3
2 4 2
3 2 3
3 6 5
4 3 3
4 5 1
5 3 1
5 6 2
def dijkstra(start):
    q=[]
    distance[start]=0
    #자기 자신의 거리는 0으로 초기화한다.
    heapq.heappush(q,(0,start))
    #힙에 거리와 노드를 넣는다.
    while q:
        dist,now=heapq.heappop(q)
        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)
distance
#결과
[1000000000, 0, 2, 3, 1, 2, 4]

 

 

매 상황에서 dist와 now로 graph에 비교하면서 cost를 갱신한다.

 

heapq에 넣을 때, 우선순위 큐를 사용하므로 cost,now순으로 push한다.