백준 1753 최단경로 - 파이썬

문제.

풀이.

다익스트라 알고리즘을 숙지하고 있어야한다.

https://ko.wikipedia.org/wiki/%EB%8D%B0%EC%9D%B4%ED%81%AC%EC%8A%A4%ED%8A%B8%EB%9D%BC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

데이크스트라 알고리즘 - 위키백과, 우리 모두의 백과사전

다익스트라 알고리즘을 알지못한다면 위의 링크를 참조하면된다.

다익스트라 알고리즘은 모든 플로이드 와셜 알고리즘과 달리 해당 정점에서 모든 정점까지의 최단 거리를 찾는 알고리즘이다.

플로이드 와셜은 모든 정점에서 출발해서 모든 정점까지의 최단 경로를 찾는 알고리즘이다.

우선 구현을 우선순위 큐를 이용하여 코드를 작성했다.

 

소스코드.

import sys
import heapq

def route(start):

    dijkstra[start] = 0 # 시작하는 정점 가중치는 0으로
    heapq.heappush(heap,[0, start]) # 우선순위 큐에 가중치과 시작 정점 삽입

    while heap:
        now_weight, now = heapq.heappop(heap)

        # 현재 테이블과 비교하여 더 가중치가 크다면 무시
        if dijkstra[now] < now_weight:
            continue

        for weight, next in graph[now]:
            next_weight = now_weight + weight # 현재 정점에서 다음 정점까지의 가중치

            if next_weight < dijkstra[next]: # 해당 테이블의 가중치가 현재 정점에서 다음 정점까지의 가중치보다 크다면
                dijkstra[next] = next_weight # 가중치 업데이트
                heapq.heappush(heap, [next_weight, next]) # 우선순위 큐에 삽입

V, E = map(int, sys.stdin.readline().split())  # 정점, 간선 입력받기
INF = sys.maxsize
start = int(sys.stdin.readline()) - 1 # 시작 정점

graph = [[] for i in range(V)]
dijkstra = [INF] * V
heap = []
# 간선과 가중치 정보 입력받기
for i in range(E):
    u, v, w = map(int, sys.stdin.readline().split())
    graph[u-1].append([w, v-1])
route(start)
for i in range(0, V):
    print("INF" if dijkstra[i] == INF else dijkstra[i])