ダイクストラの最短経路アルゴリズム

今日はダイクストラの最短経路アルゴリズムについて話します

Dijkstraの最短経路アルゴリズムの定義

ダイクストラの最短経路は、重み付けグラフの頂点間の最短経路を計算するために博士Edger - Jjkstraによって作成されたアルゴリズムです

重み付きグラフの例

ダイクストラの最短経路応用

道路網

電気系統

グーグルマップ

ソーシャルネットワーキングアプリ

飛行の議題

IPルーティング
more details

Pythonにおけるダイクストラの最短路実装

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/

ハッピーコーディング!