Dijkstra의 최단 경로 알고리즘

Dijkstra의 최단 경로 알고리즘 정의

가중 그래프의 예

Dijkstra의 최단 경로 응용 프로그램

파이썬에서 Dijkstra의 최단 경로 구현

def dijkstraShortestPathAlgo(nodes, edges, source_indedx = 0):
    """
        code from 
        => [https://www.youtube.com/watch?v=VnTlW572Sc4]
    """
    path_lengths = {v:float('inf') for v in nodes}
    path_lengths[source_index] = 0
    adjacent_nodes = {v:{} for v in nodes}
    for (u, v), w_uv in edges.items():
        adjacent_nodes[u][v] = w_uv
        adjacent_nodes[v][u] = w_uv
    temporary_nodes = [v for v in nodes]
    while len(temporary_nodes) > 0:
        upper_bounds = {v: path_lengths[v] for v in temporary_nodes}
        u = min(upper_bounds, key=upper_bounds.get)
        temporary_nodes.remove(u)
        for v, w_uv in adjacent_nodes[u].items():
            path_lengths[v] = min(path_lengths[v], path_lengths[u] + w_uv)
    return path_lengths

참조 및 유용한 리소스