백준 1753 최단경로

최단경로

문제는 백준에서 확인 할 수 있다.

✔ 접근방법

• 다익스트라 문제
  하나의 시작 정점으로부터 모든 다른 정점까지의 최단 경로를 찾는 알고리즘

1. 그래프를 딕셔너리형태로 입력 받음
   1-1. 정점간 여러개의 간선이 있는 경우, 최솟값 하나만 입력받도록 갱신
2. 출발 정점에서부터 시작하여, 방문하지 않은 정점 중 간선의 가중치가 가장 짧은 노드를 하나씩 탐색
3. 원래 알고있던 가중치보다, 새로운 정점을 거쳐가는 가중치가 짧다면, 알고있던 가중치를 갱신

✔ 코드

import sys, heapq

def solution(V, E, start, graph):
    distances = {node: float('inf') for node in graph}  # start로 부터의 거리 값을 저장하기 위함
    distances[start] = 0  # 시작 값은 0이어야 함
    queue = []
    heapq.heappush(queue, [distances[start], start])  # 시작 노드부터 탐색 시작 하기 위함.

    while queue:  # queue에 남아 있는 노드가 없으면 끝
        current_distance, current_destination = heapq.heappop(queue)  # 탐색 할 노드, 거리를 가져옴.
        if distances[current_destination] < current_distance:  # 기존에 있는 거리보다 길다면, 볼 필요도 없음
            continue
        
        for new_destination, new_distance in graph[current_destination].items():
            distance = current_distance + new_distance  # 해당 노드를 거쳐 갈 때 거리
            if distance < distances[new_destination]:  # 알고 있는 거리 보다 작으면 갱신
                distances[new_destination] = distance
                heapq.heappush(queue, [distance, new_destination])  # 다음 인접 거리를 계산 하기 위해 큐에 삽입
        
    return distances


if __name__ == "__main__":
    V, E = map(int, (input().split()))
    K = int(input())

    graph = {node : {} for node in range(1, V+1)}
    for _ in range(E):
        u,v,w = (map(int, sys.stdin.readline().rstrip().split()))
        if graph[u].get(v, None) == None or graph[u][v] > w:
            graph[u][v] = w

    # print(graph)

    ret = solution(V, E, K, graph)
    
    for i in range(1,V+1):
        if ret[i] == float('INF'):
            print("INF")
        else:
            print(ret[i])

☝ 팁

• 파이썬을 이용하면 그래프의 표현을 딕셔너리로 쉽게 할 수 있다.
• 가중치가 짧은 간선을 탐색할 때, 우선순위 큐를 사용해야 다익스트라 알고리즘의 시간복잡도가 O((v+e)logn)이 된다.
• python으로 다익스트라 구현하기