[Python]최단경로 백준 1753

   문제

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

다익스트라 알고리즘을 사용하여야 한다.

위키를 통해 다익스트라 알고리즘을 살펴보자.

다익스트라 알고리즘이란  도로 교통망 같은 곳에서 나타날 수 있는 그래프에서 꼭짓점 간

의 최단 경로를 찾는 알고리즘이다.원래 알고리즘은 두 꼭짓점 간의 가장 짧은 경로를 찾는 

알고리즘이지만, 더 일반적인 변형은 한 꼭짓점을 "소스" 꼭짓점으로 고정하고 그래프의 

다른 모든 꼭짓점까지의 최단경로를 찾는 알고리즘으로 최단 경로 트리를 만드는 것이다.

최단 경로 알고리즘은 네트워크 라우팅 프로토콜에서 널리 이용되며, 특히 

IS-IS (Intermediate System to Intermediate System)와 OSPF(Open Shortest Path First)에

서 주로 사용된다. 또한 데이크스트라 알고리즘은 존슨 알고리즘 같은 알고리즘의 서브루

틴으로 채택되었다.윗부분만 가져왔다. 밑에 부분도 굉장히 흥미로운 내용이 많으니 

읽어보는게 좋을거같다.

https://namu.wiki/w/%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BC%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

여기서 의문점이 드는게 하나가있다.

왜 우선순위 큐를 사용할까 어차피 bfs같은 방식으로 진행하면서 연결된 모든경로를 

탐색하는거 아닌가?

http://jaegualgo.blogspot.com/2017/07/dijkstra-priority-queue.html

위 사이트를 보면 알 수 있다.

각 다음노드를 큐에 넣고 꺼내는 과정에서 그냥 큐를 사용한다면 특정노드가 바뀔시 

연결된 모든 노드의 계산값을 바꾸어야 하는 경우가 생길 수 있다. 이 경우를 최소화 

하기 위해 우선순위 큐를 사용한다면 해당 문제를 해결할수있다.

일반큐를 사용할시 O(V^2)의 시간복잡도를 가질수 있지만우선순위큐를 사용한다면

 O(ElogV)의 시간복잡도를 가지게된다.

import sys
import heapq
 
 
 
INF=sys.maxsize
V,E=map(int,sys.stdin.readline().split())#정점개수 간선개수
 
 
 
G=[[] for _ in range(V+1)]#그래프 저장
K=int(sys.stdin.readline())#시작점
 
 
 
for _ in range(E):#간선받아서 그래프에 저장
    start,end,distance=map(int,sys.stdin.readline().split())
    G[start].append([distance,end])
 
 
 
 
 
result=[INF for _ in range(V+1)]#결과저장
result[K]=0
 
 
 
#
 
q=[]#우선순위 큐
heapq.heappush(q,[0,K])#거리를 앞에두어 우선순위 큐에 넣을때 거리가 비교되도록한다.
 
 
while q:
    dis,end=heapq.heappop(q)#큐에서 pop
    for d,x in G[end]:#연결된 노드 탐색
        d+=dis#이전거리와 현재 연결된 노드의 거리를 더해서
        if d<result[x]:#거리비교 #거리가 이전보다 짧으면
            result[x]=d#거리를 갱신시키고
            heapq.heappush(q,[d,x])#우선순위 큐에 넣어준다.
 
 
for i in range(1,V+1):
    print(result[i] if result[i]!=INF else "INF")

조금 더 최적화 해보자면 연결된 노드를 검사하기전에 해당경로까지의 경로가 이전보다

 길다면 검사할필요가없다.연결된 노드를 돌기전 점검하는 구문을 넣으면 더 좋을거 같

다.

해당 부분만 수정해주자

import sys
import heapq
 
INF=sys.maxsize
V,E=map(int,sys.stdin.readline().split())#정점개수 간선개수
 
G=[[] for _ in range(V+1)]#그래프 저장
K=int(sys.stdin.readline())#시작점
 
 
 
for _ in range(E):#간선받아서 그래프에 저장
    start,end,distance=map(int,sys.stdin.readline().split())
    G[start].append([distance,end])
 
 
 
result=[INF for _ in range(V+1)]#결과저장
result[K]=0
 
#
 
q=[]#우선순위 큐
heapq.heappush(q,[0,K])#거리를 앞에두어 우선순위 큐에 넣을때 거리가 비교되도록한다.
 
 
while q:
    dis,end=heapq.heappop(q)#큐에서 pop
########################최적화
 
    if result[end]<dis:#해당 경로가 이전경로보다 길다면 연결된 노드에 대해 탐색할필요가없다.
 
        continue
 
##############################
    for d,x in G[end]:#연결된 노드 탐색
        d+=dis#이전거리와 현재 연결된 노드의 거리를 더해서
        if d<result[x]:#거리비교 #거리가 이전보다 짧으면
            result[x]=d#거리를 갱신시키고
            heapq.heappush(q,[d,x])#우선순위 큐에 넣어준다.
 
 
 
for i in range(1,V+1):
    print(result[i] if result[i]!=INF else "INF")
 
 

단순히 생각해 봤을때는 우선순위 큐를 형성하는 과정에서도 시간이 소요되기에 일반 

큐를 사용하는 방법도 괜찮아보이지만여러 상황을 고려해 봤을때 우선순위 큐를 사

용하는 편이 중복계산을 줄여 더 나은 결과를 가져올수 있을것이다.