다익스트라 알고리즘 (1753 최단경로)

단일 출발지 최단 경로( Single Source Shortest Path )

하나의 출발점에서 각 정점까지 도달하는데 비용을 계산하여 최단경로를 구하는 것에는 두가지

다익스트라 알고리즘과 벨만-포드 알고리즘이 있다.

다익스트라와 벨만-포드의 차이는 음의 가중치를 다룰수 있냐 없냐의 차이이다.(벨만-포드가 가능)

 

다익스트라 알고리즘은 최소힙을 이용하여 구현할 수 있다.

1. 우리가 알아볼 시작지점으로부터 다른 도착지점까지의 가중치 배열을 INF로 초기화한다.ans=[INF]*(v+1)
2. 시작지점의 값을 0으로 초기화하고 heap에 (가중치,위치)을 넣어준다
3. while문을 사용하여 heappop을 통하여 최소값을 뽑아주고 뽑힌 (가중치+위치에 연결된 곳들의 가중치)로 연결된 곳들을 relax(경로가 더 효율적이면 갱신해주는 것)해준다.
4. relax 될 때 다시 그 값들을 heap에 넣는다. 힙이 없어질 때 까지 반복해준다.

 

def dijkstra(k):
    ans[k]=0
    heappush(heap,[0,k])
    while heap:
        weight,num=heappop(heap)
        if weight>ans[num]:
            continue
        else:
            for c,b in adj[num]:
                if weight+c<ans[b]:
                    ans[b]=weight+c
                    heappush(heap,[ans[b],b])

이 코드를 통하여 k지점에서부터의 모든 좌표에 최단경로들을 알 수 있다.

 

1753 최단경로

https://www.acmicpc.net/problem/1753

 

1.접근

시작지점이 주어지고 시작지점으로부터의 모든 거리를 구하는 것이므로 다익스트라로 푼다

2.풀이

다익스트라 알고리즘을 적용하여 시작값을 넣어주고 최종값을 구할 때 INF를 문자열INF로 바꿔줘야한다

3.코드

 

	import sys
	from heapq import *
	input=sys.stdin.readline
	def dijkstra(k):
	ans[k]=0
	heappush(heap,[0,k])
	while heap:
	weight,num=heappop(heap)
	if weight>ans[num]:
	continue
	else:
	for c,b in adj[num]:
	if weight+c<ans[b]:
	ans[b]=weight+c
	heappush(heap,[ans[b],b])
	v,e=map(int,input().split())
	k=int(input())
	INF=sys.maxsize
	adj=[[]for _ in range(v+1)]
	ans=[INF]*(v+1)
	heap=[]
	for _ in range(e):
	a,b,c=map(int,input().split())
	adj[a].append([c,b])
	dijkstra(k)
	for i in ans[1:]:
	if i==INF:
	print('INF')
	else:
	print(i)

view raw 다익스트라.py hosted with ❤ by GitHub

 

공부한곳: https://victorydntmd.tistory.com/105?category=686701