백준 알고리즘 <최단경로>

백준 알고리즘 1753번

www.acmicpc.net/problem/1753

1753번: 최단경로

---

1753번

입력으로 첫 줄에 정점의 개수 v와 간선의 개수 e가 주어지고 둘째 줄에는 시작 정점의 번호 k가 주어진다. 그 다음 줄부터 e개의 간선 정보가 주어진다.

 

출력으로는 k에서 각 정점까지의 최단 거리를 출력하면 된다. (만약 경로가 존재하지 않을 경우에는 INF를 출력하면 된다.)

---

문제 해결

이 문제는 다익스트라 알고리즘으로 해결하면 된다.

0) 거리 배열 distance의 초기값을 무한대로 설정한다.

1) 우선순위 큐에 시작노드와 거리 0을 넣고 distance배열의 시작노드 값을 0으로 한다.

2) 우선순위 큐에서 값을 꺼낸다. -> 꺼낸 Edge의 node -> n, distance -> d

  거리 배열[n] < d면 이미 처리된 적 있는 노드이기 때문에 continue

  n과 인접한 노드들의 거리배열 값과 (d + n에서 각 인접노드로 가는 거리)를 비교해서 후자가 작다면 해당 노드의 distance 값을 후자 값으로 update하고 이를 우선순위 큐에 넣는다.

3) 2)의 과정을 우선순위 큐가 빌 때까지 한다.

---

코드

import heapq
INF = int(1e9)

def main():
    v, e = map(int, input().split())
    begin = int(input())

    distance = [INF] * (v+1)
    graph = [[] for i in range(v+1)]

    for i in range(e):
        start, end, value = map(int, input().split())
        graph[start].append((end, value))

    dijkstra(begin, distance, graph)

    for i in range(1, v + 1):
        if distance[i] == INF:
            print("INF")
        else:
            print(distance[i])

def dijkstra(begin, distance, graph):
    q = []
    distance[begin] = 0
    heapq.heappush(q, (0, begin))

    while q:
        dist, vertax = heapq.heappop(q)
        if distance[vertax] < dist:
            continue
        for i in graph[vertax]:
            cost = dist + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))

if __name__ == '__main__':
    main()

---

결과

---