이호진
최단 경로 알고리즘 - 다익스트라 - 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한다.
'주요 알고리즘' 카테고리의 다른 글
그래프 관련 알고리즘 - 다익스트라, 플로이드-워셜, 크루스칼 - 2021/05/06 (0) | 2021.05.06 |
---|---|
최단 경로 알고리즘 - 플로이드-워셜 - 2021/04/03 (0) | 2021.04.03 |
다익스트라 알고리즘 - 2021/03/22 (0) | 2021.03.22 |
크루스칼 알고리즘 - 2021/03/16 (0) | 2021.03.16 |
음료수 얼려먹기 - DFS (2021/02/22) (0) | 2021.02.22 |