dijkstra algorithm
- 다익스트라 알고리즘은 shortest path중 'Start Vertex' -> 'Dst Vertex' 이기 때문에
항상 Start dist 리스트를 중점적으로 생각한다.!!!
- 다익스트라 알고리즘에서는 가중치가 음수이면 안된다!! 0< 가중치 이어야한다.
- 아래와 같이
N
개의 Vertex와 E
개의 Edge가 차례대로 입력이된다.
6 7
1 2 4
1 3 2
2 4 4
2 5 5
3 5 4
4 6 1
5 6 2
- 본인이 편한 방식대로 graph 리스트를 만들자.
- maps 라는 그래프를 가지는 dict를 만듦
- 편의상
1
번 vertex부터 유의미한 데이터를 넣음
import sys
readl=sys.stdin.readline
V,E=map(int,readl().strip().split())
maps=[ dict() for _ in range(V+1) ]
for i in range(0,E):
V1, V2, cost=map(int, readl().strip().split())
maps[V1].update({V2:cost})
print(*maps,sep='\n')
![](https://velog.velcdn.com/images%2Fmarkyang92%2Fpost%2F88e49374-cbe2-4372-ad23-b3d9055564e8%2FIMG_E3F12C87FEB5-1.jpeg)
- dist 라는 start 입장에서 본, 가중치를 담은 리스트를 만든다.
- 기본 값으로
float('inf')
를 넣는다.
- start 의 dist만! 0으로 넣는다.
dist[start] = 0
dist=[float('inf')]*(V+1)
start=1
dist[start]=0
print(dist)
- priority queue 를 만들고, 내용은 (∑weight, vertex) 로 한다.
- 우선 순위 큐에서 ∑weight 가 낮은 순으로 min heap 정렬한다.
- ★ 첫 번째로, start -> to 로 가는 내용을 큐에 담는다. ★
pq=[]
heapq.heappush(pq, ( dist[start] , start ) )
![](https://velog.velcdn.com/images%2Fmarkyang92%2Fpost%2F93122d68-8c12-432a-9fc0-3ff85d6201de%2FIMG_611DE0B46DF6-1.jpeg)
while pq:
sig_weight, now = heapq.heappop(pq)
if dist[now] < sig_weight: continue
for to in maps[now].keys():
if sig_weight + maps[now][to] < dist[to]:
dist[to]=sig_weight+maps[now][to]
heapq.heappush(pq, ( dist[to] , to ) )
![](https://velog.velcdn.com/images%2Fmarkyang92%2Fpost%2F8b065bcf-09b6-4ca9-9641-f9ebfeda3ee5%2FIMG_D5FFB0FFF881-1.jpeg)
![](https://velog.velcdn.com/images%2Fmarkyang92%2Fpost%2F99ccced9-a769-49cc-b52f-c17e9570aa0c%2FIMG_ACC87DD5F157-1.jpeg)
import sys
import heapq
if __name__ == '__main__':
readl=sys.stdin.readline
V,E=map(int,readl().strip().split())
maps=[ dict() for _ in range(V+1) ]
for i in range(0,E):
V1, V2, cost=map(int, readl().strip().split())
maps[V1].update({V2:cost})
start=1
dist=[float('inf')]*(V+1)
dist[start]=0
print(f'dist: {dist}')
pq=[]
heapq.heappush(pq,(dist[start],start))
while pq:
sig_weight, now = heapq.heappop(pq)
if sig_weight > dist[now]: continue
for to in maps[now].keys():
if sig_weight+maps[now][to] < dist[to]:
dist[to]=sig_weight+maps[now][to]
heapq.heappush(pq,(dist[to],to))
print(f'dist: {dist}')