Dijkstra의 최단 경로 알고리즘

안녕하세요 #day_29 입니다. 오늘은 Dijkstra의 최단 경로 알고리즘에 대해 이야기 해보려고 합니다.

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

dijkstra의 최단 경로는 Edsger Dijkstra 박사가 가중 그래프에서 꼭지점 간의 최단 경로를 계산하기 위해 만든 알고리즘입니다(

가중 그래프의 예

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

도로 네트워크

전기 라인

Google 지도

소셜 네트워킹 앱

비행 의제

IP 라우팅
more details

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

Python에 익숙하지 않은 경우 다음을 확인하십시오.

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

참조 및 유용한 리소스

https://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-greedy-algo-7/

https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

https://www.freecodecamp.org/news/dijkstras-shortest-path-algorithm-visual-introduction/

행복한 코딩!!