Implementation (Part 1)
Coddyの「ベルマン–フォード法 - グラフアルゴリズム」コースのレッスン 5/9。
まず、すべてのエッジに対して1回の緩和パスを行います。
チャレンジ
中級ベルマン–フォード法は、1つの操作を繰り返すものです。それは、すべてのエッジに対する緩和パスです。まずは1回分のパスを作成しましょう。
n、フラットな edges 配列（3つの値の組、有向、負の値の可能性あり）、および source を受け取る relaxAll という名前の関数を作成してください。dist[source] = 0 とし、それ以外を無限大として開始し、次にすべてのエッジを一度だけ（与えられた順序で）緩和し、まだ到達できない頂点には -1 を使用して、結果の距離を返します。
1パスのみであるため、複数のエッジを経由してのみ到達可能な頂点は、依然として -1 のままになる可能性があります。それは想定通りです。
自分で試してみよう
#include <stdlib.h>
int* relaxAll(int n, int* edges, int edges_size, int source, int* returnSize) {
// ここにコードを記述してください
*returnSize = 0;
return edges;
}
腕試しこのレッスンには短いクイズがあります。レッスンを始めて解答し、進捗を記録しましょう。
ベルマン–フォード法 - グラフアルゴリズムのすべてのレッスン
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity