0Pricing
Competitive Programming Academy · レッスン

Bellman-Ford と負辺

負の辺を処理し、サイクルを検出します

「Bellman-Ford と負辺」はCoddyKit上の無料Competitive Programming Academyレッスンです。 これはレッスン3/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCompetitive Programming Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Competitive Programming Academyコースには全4レッスンが含まれています。

Dijkstraが失敗する場合

Dijkstraは、取り出した距離が確定値だと仮定します。しかし、後から負の辺によって経路のコストがさらに下がることがあるため、正しく動きません。

Bellman-Fordの登場

Bellman-Fordは負の辺の重みを扱えます。Dijkstraより遅いものの、貪欲法を信頼できない場合でも堅牢に動作します。

基本操作

すべての辺を繰り返し緩和します。dist[u] と辺の重みの合計が dist[v] より小さければ、dist[v] をその値に更新します。

if dist[u] + w < dist[v]:
    dist[v] = dist[u] + w

何ラウンド必要か

最短経路に含まれる辺は最大で V - 1 本です。そのため、すべての辺をV-1ラウンド緩和すれば、すべての距離を確定できます。

for _ in range(n - 1):
    relax_all_edges()

距離を初期化する

Dijkstraと同じように、始点を0、それ以外のすべての距離を無限大にして開始します。

dist = [float('inf')] * n
dist[src] = 0

1回の全走査

各パスでは、辺のリスト全体を1回走査し、各辺を緩和します。改善は、1回のパスにつき1つ先のノードへ広がります。

for u, v, w in edges:
    if dist[u] + w < dist[v]:
        dist[v] = dist[u] + w

V-1回で十分な理由

k回のパスの後には、辺をk本使う最短経路がすべて正しくなります。V-1回のパスを終えれば、すべての単純最短経路が完成します。

追加の1回

もう1回パスを実行します。それでも距離が下がるなら、コストが下がり続けていることになり、負閉路の存在を示します。

負閉路の検出

負閉路があると有限の最短経路は存在しません。無限にその閉路を回って、コストを限りなく下げられるためです。

for u, v, w in edges:
    if dist[u] + w < dist[v]:
        return 'negative cycle'

計算時間

V回のパスでE本の辺を緩和するため、Bellman-Fordの計算量はO(V * E)です。小規模から中規模のグラフに適しています。

DijkstraとBellman-Ford

辺の重みが非負で速度を重視するならDijkstraを選びます。負の重みがある場合や、問題のある閉路を検出する必要がある場合はBellman-Fordを選びます。

確認問題

V-1回のパスの後、追加のパスでも距離が下がりました。これは何を意味しますか？

まとめ：Bellman-Ford

すべての辺をV-1回のパスで緩和し、さらに1回実行して負閉路を検出します。計算量はO(V*E)ですが、Dijkstraでは扱えない場合にも機能します。✅

よくある質問

「Bellman-Ford と負辺」レッスンは無料ですか？

はい。「Bellman-Ford と負辺」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Competitive Programming Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Competitive Programming Academyコースには全4レッスンが含まれています。

「Bellman-Ford と負辺」で何を学びますか？

負の辺を処理し、サイクルを検出します ブラウザで直接実行するハンズオンコードでCompetitive Programming Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

Competitive Programming Academyを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのCompetitive Programming Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン3/4です。

「Bellman-Ford と負辺」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

このCompetitive Programming Academyレッスンでコードを書いて実行できますか？

はい。すべてのCompetitive Programming Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

このコースのすべてのレッスン

  1. ヒープを使う Dijkstra 法
  2. Deque による 0-1 BFS
  3. Bellman-Ford と負辺
  4. Floyd-Warshall 全点対最短経路
← Competitive Programming Academyに戻る