この文章はPythonで書かれています.これは就職のためのコードテストです.

一番早く着く方法

最短パスアルゴリズムは、最短パスを探すアルゴリズムです.
だから「道を探す」問題とも呼ばれています.
最短パスにはいくつかの例があります.「1つのポイントから別のポイントへの最短パスが必要な場合」、「すべてのポイントから他のすべてのポイントへの最短パスが必要な場合」です.
通常はグラフィック表示が使用され、各ポイントはグラフィックで「ノード」、ポイント間で接続された道路はグラフィックで「幹線」と表示されます.

最短パスアルゴリズムは、グレースケールアルゴリズムおよびダイナミックプログラミングアルゴリズムを用いる.すなわち,最短パスアルゴリズムはグリッドアルゴリズムと動的プログラミングアルゴリズムと見なすことができる.

概要

マルチアウトレットアルゴリズムは、「ある点から別の点への最短パスが必要な場合」に使用できる最短パスアルゴリズムである.これに対してflowersalアルゴリズムは、「すべての点から他のすべての点までのすべての最短パスが必要」というアルゴリズムである.
複数のカーブアルゴリズムは、各ステップで最短距離のノードを繰り返し選択します.次に、ノードを通過するパスをチェックし、最短距離でテーブルからパスをリフレッシュします.
flowersalアルゴリズムも、各ステップの「通過ノード」に基づいてアルゴリズムを実行します.ただし、アクセスされていないノードごとに最も近いノードを検索する必要はありません.ノード数がNの場合、アルゴリズム上でNステップが実行され、各ステップがO(NxN)によって「現在のノードを通過する」すべてのパスを演算することを考慮する.従って,flowersalアルゴリズムの全時間複雑度はO(NxNxN)であった.
マルチアウトアルゴリズムには1つの開始ノードしかないため,1次元リストを用いて他のすべてのノードに最短距離を格納した.これに対してfloywalshアルゴリズムは異なり、2 Dリストに「最短距離」情報を格納するのが特徴です.これは、すべてのノードから他のすべてのノードへの最短距離情報を含む必要があるためです.すなわち,2次元リストを扱う必要があるため,Nステップでは毎回O(N*N)の時間が必要となる.
さらに、多出力アルゴリズムはGRADYアルゴリズムであり、FloyWarcialアルゴリズムは動的プログラミングの特徴を有する.ノード数がNの場合、手順をN回繰り返し、「オンデマンド点火」の2 Dリストをリフレッシュするので、動的プログラミングと見なすことができます.

点火式は上記のように、「AからBまでの最低コスト」を「AからKからBまでのコスト」と比較して、より小さな価格で更新します.つまり、特定のノードを介して移動する距離よりも高速移動距離の方がコストがかかる場合は、より短い距離に更新されます.

Flowersalの実装

例

上記の図面がある場合は、次のように初期テーブルを設定します.初期状態step 1では、「接続された幹線」はこの値のみを入力し、「接続されていない幹線」は「無限」である.2 Dリストでは、各値のDabは「aからbまでの最短距離」です.
自己から自己へのコストは0であるため、(1<=i<=n)の範囲を持つすべてのiに対してDiiは0にリセットされる.

は1ノードのみを通過します.この場合、6=3工場の2つのケースを考慮するだけです.2 Dテーブルでは、次のように異なる色で色を塗り、計算する必要があります.

この6つの場合にのみ、更新値を1つずつチェックして計算します.たとえば、「2ノードから1ノード、さらに3ノードまでのコスト」が「2ノードから1ノード、さらに3ノードまでのコスト」よりも小さい場合は、再発注が必要になります.だから.𝐷_23の値は、D 23および(D 21＋D 23)より小さい値に置き換えられる.つまり、1を通過する時間が早い場合は最短距離を更新する.

上記の6つのシアン部分のすべての式を計算して値を更新すると、テーブルは次のように変更されます.例えば、D 24は、最初は「無限」の値を有し、D 21+D 14=9と比較して9に更新される.

課と同様に、アルゴリズムを順番に実行してください.これは2番ノードを経由した場合を計算する必要があるので、1番ノード、3番ノード、4番ノード(2番ノードを除く)から2つのノードを抽出することを考慮してください.具体的には,(1,3),(1,4),(3,1),(3,4,1)および(4,3)の6種類がある.

同様に、青色の部分のみを考慮すると、更新結果は次のようになります.例えば、元のD 13は、D 12+D 23=11より11に更新された「無限」の値を有する.

この手順を繰り返すノード数が

の場合、テーブルにはすべてのノードからすべてのノードまでの最短距離情報が表示されます.例えば、D 13(第1行の第3列)の値は8であり、1ノードから3ノードまでの最短距離が8であることを示す.

コード#コード#

INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정

# 노드의 개수 및 간선의 개수를 입력받기
n = int(input())
m = int(input())
# 2차원 리스트(그래프 표현)를 만들고, 모든 값을 무한으로 초기화
graph = [[INF] * (n + 1) for _ in range(n + 1)]

# 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
for a in range(1, n + 1):
    for b in range(1, n + 1):
        if a == b:
            graph[a][b] = 0

# 각 간선에 대한 정보를 입력받아, 그 값으로 초기화
for _ in range(m):
    # A에서 B로 가는 비용은 C라고 설정
    a, b, c = map(int, input().split())
    graph[a][b] = c

# 점화식에 따라서 플로이드 워셜 알고리즘을 수행
for k in range(1, n + 1):
    for a in range(1, n + 1):
        for b in range(1, n + 1):
            graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])

# 수행된 결과를 출력
for a in range(1, n + 1):
    for b in range(1, n + 1):
        # 도달할 수 없는 경우, 무한(INFINITY) 라고 출력
        if graph[a][b] == INF:
            print("INFINITY")
        else:
            print(graph[a][b], end = " ")

    print()