最短経路問題の探究: ダイクストラのアルゴリズム

[[386543]]

前回、データ構造としてのグラフについて書きましたが、グラフ アルゴリズムのテスト ポイントは最短経路問題だけです。

最短経路問題

最短経路問題: エッジに重みが付けられたネットワークが与えられた場合、パス上のエッジの重みの合計が最小になるように、指定された開始点から指定された終了点までのパスを見つけます。

たとえば、上の図では、図のポイント 1 からポイント 4 までの最短経路の長さは 3 (1 から 2 から 4) になります。

最短経路問題はダイクストラ法で解かれることが多い。

ダイクストラアルゴリズム

ダイクストラ アルゴリズムは、1 つのノードから他のすべてのノードまでの最短パスを計算するために使用される、典型的な単一ソース最短パス アルゴリズムです。開始点を中心に層ごとに外側に広がり、終了点に到達するのが最大の特徴です。

例えば、上図のダイクストラアルゴリズムは、開始ノードから隣接ノードまでのすべてのパスを継続的に検索し、初期距離を最短距離に設定し、最も遠いノードまでの最短距離が解決されるまで、隣接ノードの最短距離を継続的に更新するプロセスです。

テキストの説明が明確ではありません。下のアニメーション画像を参照してください。

グラフ上の頂点は、訪問済みノードと未訪問ノードの 2 つのセットに分割されます。

ポイントが訪問先から外側に拡張されるたびに、拡張ルールは更新可能なポイント間の距離が最小になるようにすることです。

上の写真を例に挙げてみましょう

まず、隣接行列を使用して無向グラフを表します。

最大= 9999 
 
 g=[
    [0, 1, 4, 6],
    [最大, 0,最大, 2],
    [ MAX , MAX , 0, 1],
    [ MAX 、 MAX 、 MAX 、 0]
 ]

隣接行列g[0][1]=1は、最初のノードから2番目のノードまでの距離が1であることを意味します。

目的は、出発点1から他の点までの最短経路距離を見つけることです。

 n = 4 #4 ポイント
# 訪問した場所を初期化する
visitsd = [0] * (n) #ポイントが訪問されたかどうかを記録する
# 最初のポイントを訪問しました
訪問数[0] = 1
 # ソースポイントから各ポイントまでの距離ノードセットを初期化します
d = g[0] 
 
 iが範囲(2, n)内にある場合:
    # dをトラバースし、最小の重みを持つノードの位置を取り出す
    最小重量 =最大 
 jが範囲(2, n)内にある場合:
        d[j] < minWeigthかつvisited[j] == 0の場合:
            最小重量 = d[j]
            ｋ＝ｊ
            # kが1から最短距離にある点であることを示し、kが見つかったことをマークします
    訪問数[k] = 1
    # このポイントでリラックスしましょう
jが範囲(2, n)内にある場合:
        d[j] > d[k] + g[k][j]かつvisited[j] == 0の場合:
            d[j] = d[k] + g[k][j] 
 
 iが範囲(1,n)内にある場合:
    印刷(d[i]) 
     
 1
 4
 5

これまでのところ、ノード 1 から残りの 3 つのノードまでの最短距離は 1、4、および 5 です。

「重み付けされていないグラフ、つまりすべてのエッジの重みが等しいグラフにダイクストラのアルゴリズムを適用することは、BFS 検索と同等です。」

その他のソリューション

多くの場合、無向グラフの最短経路を取得するには、一連の点を入力し、開始点を入力する必要があります。

インポート数学
# グラフの頂点の数を仮定する
V = 6
 # 配列をマークします。used[v] がFalseの場合、頂点がまだ訪問されていないことを意味します。これは S にあり、それ以外の場合は U にあります。
使用 = [ False   _が範囲内(V)]
 # 距離配列: distance[i]はソースポイントsからiまでの最短距離を表します。distance[s]=0
距離 = [ float ( 'inf' ) _の範囲(V)]
 # cost[u][v]は辺e=(u,v)の重みを表し、存在しない場合はINFに設定されます
# コスト受信テーブル
コスト = [[ float ( 'inf' ) _が範囲内(V)] _が範囲内(V)] 
 
 def dijkstra(s):
    距離[秒] = 0
    真の場合:
        # ここでの v はセンチネルと同等であり、すべての開始点 s に対して統一された処理を実行します。
        v = -1
        # 未使用の頂点からの距離が最小の頂点を選択する
uが範囲(V)内にある場合:
            使用されていない場合[u]かつ(v == -1または距離[u] < 距離[v]):
                v = u
        v == -1の場合:
            # これは、すべての頂点が S 内で維持されることを意味します。
            壊す
        # 選択した頂点をSに追加し、同時に距離を更新します
        使用[v] =真 
        # U の各頂点から開始点 s までの距離を更新します。 U 内の頂点の距離を更新する理由は、前のステップで、最短経路を見つけるための頂点として k が決定されたため、k を使用して他の頂点の距離を更新できるためです。たとえば、(s, v) の距離は、(s, k) + (k, v) の距離よりも大きくなる可能性があります。
 uが範囲(V)内にある場合:
            距離[u] =最小(距離[u]、距離[v] + コスト[v][u]) 
 
 
 _が範囲内(9)の場合:
    v、u、w = リスト(map( int 、 input().split()))
    コスト[v][u] = w
    コスト[u][v] = w
 s = int (input( '出発地を入力してください:' ))
ダイクストラ
印刷(距離)

テストケース

0 1 1
 0 2 2
 0 3 3
 1 4 7
 1 5 9
 2 4 4
 3 4 5
 3 5 6
 4 5 8
出発地を入力してください: 0
 [0、1、2、3、6、9]

テストケースでは、0 1 1 は最初の頂点から 2 番目の頂点までの距離が 1 であることを意味します。

隣接リストを使用したダイクストラのアルゴリズムの時間計算量は次のとおりです。そのため、多くの場合、最適化のためにヒープを使用したり、余分なスペースを最適化するためにハッシュ テーブルを使用したりします。