다익스트라

다익스트라는, 최단 경로 (비용이 일정하지 않을 때) 사용하는 알고리즘이다.

(비용이 일정할땐, bfs로 푸는 것이 쉬움을 이전에 배웠다.)

 

세팅 :  정답 행렬 (어디서 어디로 갈때 얼마나 비용이 드나) 를 무한대로 초기화 (n,n은 0으로 초기화)

0.출발 노드를 우선순위 큐에 넣는다.

1. 처음 입력받은 거리 행렬 중, 현재 인덱스 -> 갈 수 있는(아직 안 간) 가장 값이 작은 노드 선택

2. 해당 노드까지 가는 비용 ex ) 1->4 >>> 정답행렬의 해당 노드 [ex )정답행렬[1] ] + 기존 행렬의 1->4 

3. 업데이트가 실행 되면,  그 값을 정답행렬에서 바꾼다. 

4. 업데이트가 실행 되면,  그 INDEX를 우선순위 큐에 넣는다. (주로 HEAPQ로 구현한다. 정렬을 안해도 되므로)

5. 그 과정에서, VISITED 노드면 다시 확인하지 않는다. 

 

#일단, 정답 행렬은 만약 출발점이 지정되어있다면 1차원 행렬만으로도 충분히 가능하다. 

 

import sys
import heapq

V,E = map(int,sys.stdin.readline().split())
K =int(input())
visited = [False] * (V+1)
answerlist = [sys.maxsize]*(V+1)
graph = [[] for _ in range(V+1)]

for i in range(E) :
    inputlist = list(map(int,sys.stdin.readline().split()))
    u = inputlist[0]
    v = inputlist[1]
    w = inputlist[2]

    graph[u].append([v,w])


q = []
heapq.heappush(q,[0,K])
answerlist[K] = 0 


while q :

    nowarr = heapq.heappop(q)
    nowindex = nowarr[1]

    #방문한 적이 있는가? 없으면 추가
    if visited[nowindex]==True :
        continue
    visited[nowindex] = True

    for cangolist in (graph[nowindex]) :

        cangocost = cangolist[1]
        cangonext = cangolist[0]
        if answerlist[cangonext] > answerlist[nowindex] + cangocost :
            answerlist[cangonext] = answerlist[nowindex] + cangocost
            heapq.heappush(q,[answerlist[cangonext], cangonext])

for i in range(1,len(visited)):
    if visited[i] == True :
        print(answerlist[i])
    else :
        print("INF")

 

결국 핵심은

1. heapq를 통해서 우선순위 큐 생성 . 

2. 방문여부 찾는 배열

3. 최종 정답 배열 생성

4. 출발점 넣어주기 (heapq에)

5. heapq가 빌때까지, heapq에서 현재 index위치 뽑기

6. 해당 index에서, input graph를 보고 다음 index까지 중 가장 짧은 친구 찾기 

7. 그렇게 찾고 나면 , 그 출발 -> 마지막 > 출발 -> 현재 index + 현재 index+ 다음 짧은 친구 인지 확인

8. 맞다면, heapq에 푸시 

9. 맞다면, 정답 배열에도 그 값을 넣어주기 

 

정리해보기

 

구현은?

1. v,E로 리스트 만들기

2. visited list 만들기

3. 해당 list의 값들을 모두 무한으로 초기화

4. 그다음에 간선 값을 입력 받아서, 어디서 어디까지 가는 비용 얼마인지 다시 초기화

5. 현재 노드에서, 다음 노드까지 값 중 가장 짧은 노드 반환

6. 현재노드가 종료노드가 될때까지 반복.

 

근데, 최고의 노드를 선정하는게 긴시간이 걸린다 - MST

1. NLIST를 인접 행렬로 받는다 -> 3->(2까지,3비용) TUPLE로 <해당 nlist값은 변경되지 않는다>

2. Distances[목표 index]=> 시작점->해당index까지의 최종 거리를 저장하는 배열(최초 inf)

3. heap을 사용한다. (heap에는 (시작부터 해당거리,다음 갈 곳) ex) 1->4->3 (4까지 거리, 다음3)

4. 1->3 (distance값) 과 1->4(heap에 들어가있는 해당거리) + 4->3 (nlist배열을 돌며 계산)
하여 더 작은 값을 distanc에 넣는다

5. 최종 계산.

 

이와 같이 heapq를 활용하는게 MST이다.