白駿11657号:タイムマシン

問題解決の考え方

グラフィック理論

ベルマンフォードアルゴリズム

✔アルゴリズムの説明
ベルマン・フォードアルゴリズムを学習した後,コードを記述した.
https://www.youtube.com/watch?v=Ppimbaxm8d8参照.

ベルマンフォードアルゴリズムの特徴:

マルチ出口アルゴリズムと同様に、ある点から別の点までの最短距離を求めるアルゴリズムである.

重み付けが負数の場合に使用します.

負周期が存在するか否かを判断することができる.

とマルチ出口アルゴリズムの比較

アルゴリズムは最短距離が最も短い点から検出を開始するので,一度に検出した点は検出されない.

とは対照的に、ベルマン・フォードアルゴリズムは、すべての「幹線」を確認するプロセスを経て、このプロセスはV−1回繰り返し実行されるので、重み付けが負の値である場合を考慮することができる.

マルチ出力アルゴリズムの時間複雑度はO(V^2)である.これは、全ての点(V)を繰り返し、長さVのテーブル毎に最短距離の点(V)を選択するためである.

Heapのマルチアウトレットアルゴリズムを用いた場合はO(EGV)である.これは、支点に付いている幹線数に従って(E)を繰り返し、Heapを用いて最短距離(logV)の支点しか選択できないためである.

ベルマン‐フォードアルゴリズム(V‐1)は全幹線(E)を反復的に考慮し,時間複雑度はO(VE)であった.

✔完全コード

import sys
INF = float('inf')

N, M = map(int, sys.stdin.readline().split())

graph = {}  # 전체 graph는 dictionary임
for i in range(N):
    graph[i+1] = []  # 각 지점마다 각자의 array를 가지고 있음
for _ in range(M):
    A, B, C = map(int, sys.stdin.readline().split())
    graph[A].append([B, C])  # index 0이 지점, index 1이 비용인 array를 넣어줌

dist = [INF]*(N+1)


def bellman_ford(start):
    dist[start] = 0
    for i in range(N):
        for a in range(1, N+1):
            for b, c in graph[a]:
                if dist[b] > dist[a] + c:
                    dist[b] = dist[a] + c
                    if i == N-1:
                        return True
    return False


negativeCycle = bellman_ford(1)
if negativeCycle:
    print("-1")
else:
    for i in range(2, N+1):
        if dist[i] == INF:
            print("-1")
        else:
            print(dist[i])

ベルマンフォードアルゴリズムフロー

開始ノードを設定し、最短距離テーブルを初期化します.

dist = [INF]*(N+1)
dist[start] = 0

本の幹線Eを1本ずつ検査し、各幹線を経由して別のノードへの費用を計算し、表を更新する.
そしてこの過程をN-1回繰り返します

for i in range(N-1):  # 한번에 특정지어버리는 다익스트라와 다르게 N-1번 반복
    # 밑의 2중 for문의 최대 반복 횟수가 간선의 개수와 같으므로 시간복잡도 O(E)
    for a in range(1, N+1):  
        for b, c in graph[a]:  # (각 지점에서 연결된 간선의 개수만큼 반복)
            if dist[b] > dist[a] + c:
                dist[b] = dist[a] + c

の負のシーケンスループが発生しているかどうかを調べるために、N−1より1回繰り返した.
このとき最短距離テーブルを更新すると、負の水平線ループがあると判断します.

for i in range(N):  # N-1 -> N
    for a in range(1, N+1):
        for b, c in graph[a]:
            if dist[b] > dist[a] + c:
                dist[b] = dist[a] + c
                if i == N-1:  # N번째에 갱신되면 순환이 존재하는 것으로 판단
                    return True
return False   # 그렇지 않으면 존재 안하는 것으로 판단

ベルマン・フォードアルゴリズムはN-1回繰り返して正常に動作する必要があることを覚えておいてください.