[アルゴリズム]最短パス(マルチアウトレット)

最短パス

2つのノードを接続する最短パスを探します.
重み付けマップで、[幹線重み付け和](幹線重み付け和)を最小にするパスを見つけます.
)

単点出発および単点到達(あるノードから別のノードへの最短経路)

.

単点最短経路(特定のノードと残りのノードとの間の最短経路)

.

全二重最短経路(u,v)

2番目のマルチタスクアルゴリズムを見てみましょう.

ダエストラ

最初のノードに関連付けられたノードを追加し、最短距離をリフレッシュ
(BFS類似)

アルゴリズム実装

:優先キュー(MinHeap)を使用して、現在の最短距離のノード情報を最初に抽出します.
これで距離の長い経路は計算しなくてもいいです.
1)最初のノードに対するアレイの宣言->最初のノードから各ノードまでの距離をアレイに格納します.

初期時、第1ノードの距離は0であり、残りのノードは無限大のinfとして記憶される

優先キュー(距離0、第1ノード)における優先キュー

2)優先キューからノードを取り出す.(優先キューにポップアップするノードがないまで繰り返します)

は、最初に第1のノードのみを記憶するため、第1のノードは

にポップアップされる.

の第1のノードに隣接する各ノードについて、
[最初のノードから各ノードまでの距離](Distance from First Nodes)と[現在のアレイに保存されている距離](Stored In Current Array)の比較
->最初のノードからノードまでの距離がアレイに格納されている距離よりも短い場合は、アレイ内のノードまでの距離を更新します.
->アレイでノードの距離を更新した場合は、ノード情報を優先キューに入れます.

(BFSと同様に、最初のノードに順次アクセス)
*アレイに記録されている最短距離よりも距離が大きい場合、ノードに隣接するノード間の距離は計算されません.

import heapq

def dijkstra(graph, start):
    # 노드 정보를 담을 딕셔너리 (노드번호:거리)
    distances = {node:float('inf')for node in graph}
    # 우선순위 큐 생성
    queue = []
    
    # 초기에 출발노드->자기자신의 거리는 0으로 세팅
    distances[start] = 0
    # 우선순위 큐에 (거리0, 노드번호) 추가
    heapq.heappush(queue, [distances[start], start])
    
    # 우선순위 큐가 빌 때까지 반복
    while queue:
        # 우선순위 큐에서 거리가 가장 짧은 노드정보부터 꺼냄
        cur_distance, cur_node = heapq.heappop(queue)
        # 저장된 거리가 현재 거리보다 짧을 경우 계산 건너뜀
        if distances[cur_node] < cur_distance:
            continue
            
        # 꺼낸 노드와 인접한 노드들 각각에 대해!!
        for adj, weight in graph[cur_node].items():
            # 현재 거리에 인접 노드까지 가는 거리를 더함
            distance = cur_distance + weight
            
            # 새로 계산한 거리가 저장된 거리보다 짧을 때
            if distance < distaces[adj]:
                # 해당 노드의 거리를 업데이트하고,
                distances[adj] = distance
                # 우선순위 큐에 해당 노드 정보 넣기
                heapq.heappush(queue, [distance, adj])
    return distances

時間の複雑さ

: O(E) + O(ElogE) = O(ElogE)
プロセス1)各ノードのすべての近接幹線をチェックする=>O(E)
プロシージャ2)優先キューにノード/距離情報を配置してポップアップするプロシージャ=>O(logE)*追加時間O(E)、優先キューを保持する時間O(logE)
注)Dave LEEレッスン