그래프3-다익스트라

다익스트라

방향/무방향 그래프에서 하나의 정점에서 모든 정점까지의 최단거리를 찾아주는 알고리즘

플로이드는 음수인 간선은 문제가 없고 음수의 싸이클이 존재할때 쓸 수 없다.
다익스트라는 간선이 음수이면 사용불가하다.

O(V^+E) 복잡도

방법
출처 : 바킹독 알고리즘 (유튜브) > 링크

1. root를 check에 확정한다.
2. root-root 거리는 0으로
3. root의 거리 중에 제일 작은 값을 "확정"한다
4. "확정된 것의 벡터"를 전체를 흝는다.
   이때 ("root -> 확정된것의 벡터") vs ("root -> 확정된것" + "확정된것 -> 확정된것의 벡터") 중 작은 값을 갱신

주의
확정을 하는 값이 n개가 될때까지 돌아야한다.
이미 확정된 값은 넘어가야함

위 그림의 입력 예시

6
8
1
1 2 3
1 3 2
1 4 5
2 3 2
2 5 8
3 4 2
4 5 6
5 6 1

---

일반적인 구현

n = int(input())
e = int(input())
root = int(input())

costtable=[[10000]*(n+1) for __ in range(n+1)]
check=[0]*(n+1)
listtable = [[] for ___ in range(n+1)]
for _ in range(e):
    s,e,cost = input().split()
    s=int(s)
    e=int(e)
    cost=int(cost)
    costtable[s][e]=cost
    listtable[s].append(e)

check[root] = 1 #1. root를 check에 확정한다.
costtable[root][root] = 0 #2. root-root 거리는 0으로

while(sum(check)<6): # 확정을 하는 값이 n개가 되어야하므로 n-1까지 돌도록 함
	minn = 10000
	for rvecidx in range(1, n+1): #3. root의 거리 중에 제일 작은 값을 "확정"한다
		if check[rvecidx]: #이미 확정된 값은 넘어가야함
			continue
		if minn > costtable[root][rvecidx]:
			checknode = rvecidx
            minn = costtable[root][rvecidx]
	check[checknode] = 1 #######여기까지가 3
	for cvec in listtable[checknode]: #4. "확정된 것의 벡터"를 전체를 흝는다. 이때 ("root -> 확정된것의 벡터") vs ("root -> 확정된것" + "확정된것 -> 확정된것의 벡터") 중 작은 값을 갱신 (이건 계속 바뀐다.)
		if costtable[root][cvec] > costtable[root][checknode] + costtable[checknode][cvec]:
			costtable[root][cvec] = costtable[root][checknode] + costtable[checknode][cvec]

print(costtable[root])

논리
애초에 root의 벡터를 살필때 최소값을 확정짓기 때문에
2번 노드가 확정되었다고 하고 다른 노드를 돌아서 2번노드로 가는게 최소라 한다면,
애초에 2번노드가 확정되지 않았을 것이다.(루프의 시작에 최솟값을 확정하기 때문)
이 때문에 음수 간선을 사용할 수 없는것.

---

우선순위 큐(힙)을 이용한 다익스트라의 구현

O(ElogE) 복잡도

방법

1. 우선순위 큐에 (0,시작점)을 추가 : (거리,정점)의 의미임
2. 우선순위 큐에서 거리가 가장 작은 원소를 선택, 해당 거리가 최단거리 테이블에 있는 값과 다를 경우 넘어감
   d[팝한 값의[1]] vs 팝한 값의[0]과 비교 (거리, 정점)이므로
3. 원소가 가리키는 정점을 v라고 할 때, v와 이웃한 정점들에 대해 최단거리 테이블 값보다
   v를 거쳐가는 것이 더 작은 값을 가질 경우 최단거리 테이블의 값을 갱신하고 우선순위 큐에
   (거리, 이웃한 정점의 번호)를 추가
4. 우선순위 큐가 빌 때까지 2,3번 반복

여기서는 최단거리 테이블에서 시작-시작을 제외한 부분은 무한대(최대값)로 갱신한다.

위의 예시에 대한 구현 (경로 복원시 주석처리함) 만날때까지 while하면됨. 플로이드 추적이랑 같음

import sys
import heapq

n=int(input())
e=int(input())
root=int(input())
listtable = [[] for ___ in range(n+1)]
costt = [[3000]*(n+1) for __ in range(n+1)]
for _ in range(e):
    s,end,cost = map(int, sys.stdin.readline().strip().split())
    costt[s][end] = cost
    listtable[s].append(end)

table = [3000]*(n+1)
#pre = [3000]*(n+1) 경로 복원 시
table[root] = 0
q = []
heapq.heappush(q,(0,root))
while(q):
    cur = heapq.heappop(q) #ㄱㅓ리, 정정점
    if table[cur[1]] != cur[0]:
        continue
    for nxt in listtable[cur[1]]:
        if table[nxt] > table[cur[1]] + costt[cur[1]][nxt]:
            table[nxt] = table[cur[1]] + costt[cur[1]][nxt]
            #pre[nxt] = cur[1] 경로 복원시
            heapq.heappush(q,(table[cur[1]] + costt[cur[1]][nxt], nxt))

print(table)