다익스트라 알고리즘(dijkstra algorithm)

* 최단 경로 구하기 알고리즘의 하나
  - 다익스트라 알고리즘은, 특정한 노드에서 출발해 마지막 노드에 도착하는 것까지의 경로를 구하는 것과 관련 있다.
  - 관련 문제: 백준 10282번 - 해킹 (www.acmicpc.net/problem/10282)
                  백준 5719번 - 거의 최단 경로(www.acmicpc.net/problem/5719)

import heapq

mygraph = {
    'A':{'B':8, 'C':1, 'D':2},
    'B':{},
    'C':{'B':5, 'D':2},
    'D':{'E':3, 'F':5},
    'E':{'F':1},
    'F':{'A':5}
}

def dijkstra(graph, start):
    # 초기화
    distances = { node:float('inf') for node in graph }
    distances[start] = 0
    queue = []
    heapq.heappush(queue, [distances[start], start])

    # 반복문
    while queue:
        cur_route_distance, cur_node = heapq.heappop(queue)

        if distances[cur_node] < cur_route_distance:
            continue

        for adjacent, weight in graph[cur_node].items():
            distance = cur_route_distance + weight

            if distance < distances[adjacent]:
                distances[adjacent] = distance
                heapq.heappush(queue, [distance, adjacent])

    return distances

print(dijkstra(mygraph, 'A'))
""" {'A': 0, 'B': 6, 'C': 1, 'D': 2, 'E': 5, 'F': 6} """

- 최단 경로 출력하기

import heapq


def dijkstra(graph, start, end):
    distances = {node: [float('inf'), start] for node in graph}
    distances[start] = [0, start]

    queue = []

    heapq.heappush(queue, [distances[start][0], start])

    while queue:
        cur_route_distance, cur_node = heapq.heappop(queue)

        if distances[cur_node][0] < cur_route_distance:
            continue

        for adjacent, weight in graph[cur_node].items():
            distance = cur_route_distance + weight

            if distance < distances[adjacent][0]:
                distances[adjacent] = [distance, cur_node]
                heapq.heappush(queue, [distance, adjacent])

    path = end
    path_output = end + '->'
    while distances[path][1] != start:
        path_output += distances[path][1] + '->'
        path = distances[path][1]
    path_output += start
    print(path_output)
    return distances


mygraph = {
    'A': {'B': 8, 'C': 1, 'D': 2},
    'B': {},
    'C': {'B': 5, 'D': 2},
    'D': {'E': 3, 'F': 5},
    'E': {'F': 1},
    'F': {'A': 5}
}

print(dijkstra(mygraph, 'A', 'F'))

- 출처 :
    - Fastcampus
    - 잔재미코딩(www.fun-coding.org/Chapter20-shortest-live.html)