最短パスアルゴリズムとは?

최단 경로 알고리즘は、2つのノードを接続する最短パスを検索するアルゴリズムである.重み付けパターンでは,幹線重み付けと最小化の経路を探すことは符号化試験でよく発生する問題ではないと思うが,この点に注意すべきである.😱

エンコードテストで最も短いパスの問題のタイプ

単点出発と単点到達(単点源と単点目的地の最短経路問題)最短経路問題

図中のあるノードuから、別のノードvに到達最短経路の問題

を探す.

単点出発(single-source and最短経路問題)最短経路問題
問題

グラフィック内の特定のノードuおよびグラフィック内の他のすべてのノードの最短パス

を検索する.

全対(all-pair)最短パス:グラフィック内のすべてのノード対(u,v)の最短パスを検索する問題

複数の曲線アルゴリズムは、1つの頂点から別の頂点までの最短距離を求める問題であり、上述した最短経路問題の2番目に相当する.

Dijkstraアルゴリズムロジック

다익스트라(Dijkstra)アルゴリズムは、第1の頂点に基づいて接続された頂点を追加し、最短距離を更新する方法によって、그래프 탐색の古典的なアルゴリズム너비 우선 탐색(BFS)と同様である.
エクスポートアルゴリズムの変換ロジックはいくつかありますが、最も改善された優先度キューを使用します.
まず,マルチアウトプットアルゴリズムを記述するためのグラフィックを取得する.

ステップ1:初期化

配列が最初の頂点に対して相対することを宣言して、最初の頂点から各頂点までの距離を保存します.

初期時、第1頂点の距離は0であり、残りの無限記憶

である.

優先キューには、最初の頂点(距離0)

のみが配置する.

ステップ2：優先順位キューから抽出した（A，0）［ノード，1番目のノードからの距離］から隣接ノードからの距離を算出する

우선순위 큐では、第1の頂点に隣接するノードの距離を比較し、優先順位キューに配置する.

は、最初に第1の頂点のみを記憶するため、第1の頂点は

にポップアップされる.

の第1の頂点に隣接する各ノードについて、第1の頂点から各ノードまでの距離を、現在の配列に格納されている第1の頂点から各頂点までの距離と比較する

.
第1の頂点からノードまでの距離が

アレイに記憶する距離よりも短い場合、そのノードの距離

がアレイに更新される.

アレイにおいてノードの距離が更新された場合、優先キュー

に入れる.

すなわち、頂点以外のすべてのノードがinfであるため、第1の頂点に隣接するすべてのノードが優先キューに入り、第1の頂点に隣接するノード間の距離が配列に更新される.(ノードへのアクセスは、너비 우선 탐색と非常に類似しています.)

ステップ3：優先キュー（C，1）［ノードと最初のノードの距離］から隣接ノードとの距離を計算する

Pythonでは우선순위 큐が最小ヒップ数であるため、ステップ2の表では、まず(C,1)、(D,2)、(B,8)(C,1)を抽出する.
A-B最短距離が8の場合

A-Cまでの距離は(C,1)B,D-C-Bは5,すなわちA-C-Bは1+5=6であるため,A-B最短距離8よりも小さい距離

が見出された.

アレイに更新(アレイで更新されているため、AからBまでの最短距離(B,6)値が優先キューに格納)

.

C-Dの距離は2、すなわちA-C-Dは1+2=3であり、A-Dの現在の最短距離2よりも長いため、Dの距離は

更新されない.

ステップ4：優先キュー（D，2）［ノード，1番目のノードからの距離］から隣接ノードの距離を計算する

Aの隣接ノードのみにアクセスする場合、EとFの間の距離が計算される.
距離

A-Dの2,D-Eは3,プラス(E,5)

距離

A-Dの2ウェイD-Fは5であり、さらに(F,7)

を加える.

ステップ5:優先キュー(E,5)[ノード,1番目のノードからの距離]から隣接ノードの距離を計算する

A−E距離が5の場合、Eに隣接するFの距離は1、すなわちA−E−Fは5+1=6であり、現在のアレイA−Fの最短距離は7であるため、(F,6)に更新される.

優先キューに追加(F,6)

ステップ6：優先順位キューから（B、6）、（F、6）を順に抽出し、各ノードに基づく隣接ノードとの距離を算出する

例示的なグラフィックでは、Bノードは他のノードのルートノードに通じていないため、パスがあり、FノードはルートノードがAノードに通じているが、現在のA-Aは0であり、A-F-Aは6+5=11であるため、更新できない.

ステップ7:優先順位キューから(F,7)、(B,8)を順に抽出し、各ノードに基づく隣接ノードとの距離を算出する

A-Fのルートまでの距離は7ですが、配列内の現在の最短距離は6であるため、通過します.(B,8)A−B距離が6であるため、A−B距離を計算する必要もない.

マルチカーブアルゴリズムの実装

import heapq

def dijsktra(graph, start):

    # 무한대로 넣음
    distances = {node: float('inf') for node in graph}

    # 그래프의 시작 정점 거리는 0으로 초기화
    distances[start] = 0

    # 모든 정점이 저장될 큐 생성
    queue = []

    # 그래프의 시작 정점과 거리를 최소힙에 넣음
    heapq.heappush.(queue, [distances[start], start])

    while queue:
        current_distance, current_node = heapq.heappop(queue)

        # 지금까지의 거리가 발견한 거리보다 더 작다면 다음 단계 패스
        if distances[current_node] < current_distance:
            continue

        # 인접노드, 거리 값
        for adjacent, weight in graph[current_node].items():
            distance = current_distance + weight

            # 최단거리를 발견했을 경우 거리를 업데이트
            if distance < distances[adjacent]:
                distances[adjacent] = distance
                heapq.heappush(queue, [distance, adjacent])

    return distance