다익스트라 정리

최단 경로 정리

• 간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중에 간선의 가중치의 합이 최소인 경로

다익스트라 알고리즘

• 하나의 시작정점에서 끝 정점까지의 최단경로(최소비용)
• 음의 가중치를 고려하지 않음
• cf) 벨만-포드 알고리즘 (음의 가중치 허용), 플로이드-워샬(모든 정점들에 대한 최단 경로)

• 연습문제 : SWEA5250

# 문제의 아이디어

# dfs든 bfs든 다익스트라든,,, 시작 정점을 정하고, 어디로 이어나갈 것인지를 생각해야한다. 
# 이어나가면서, 비교해야할 값들에 대한 정의를 살펴보고 같이 전개해나가면 된다.



def van_dijk():
	while q:
    # 시작 되는 곳은 0이었고, 처음 이동한 곳 받아옴
    	now, cost = q.pop(0)   
    	
        
        # adjlist의 길이 만큼만
        for i in range(len(adjlist[0])):  
        	next_i, next_cost = adjlist[0][i]  # 다음으로 갈 곳을 찾아주자
            if cost + next_cost < d[next_i]  # 0번에서 이동한 곳보다 작다면
            	d[next_i] = cost + next_cost # 저장
                q.append((next_i, d[next_i]))
        
        
t = int(intput())
for tc in range(1, t+1):
	V, E = map(int, input().split())  # 입력 값 받아주기
    adjlist = [[] for _ in range(V+1)) # V+1 만큼 인접리스트 생성
    infinity = 1000000  # 문제보고 무한대로 할만한 값 임의 입력
    for _ in range(E):
    	s, w , e = map(int, input().split())
        # 인접리스트의 인덱스 s는 시작 지점이므로, 시작지점의 인덱스에 
        # 어디로 갈 것인지, 가중치는 얼마인지를 저장
        adjlist[s].append((w,e))
        
    # 출발 지점에서 갈 수 있는 곳들의 가중치 기록
    d = [infinity] * (V+1) 
    for w,e in adjlist[0]:
    	d[w] = e   #[0,1,6]
    
    q = [*adjlist[0]]
    van_dijk()  # 반 다이크스트라