最短パスアルゴリズム-Floydアルゴリズム
Floydアルゴリズム
データ構造図論の最短パスアルゴリズムは、古典的な3つがあります.*Floyd Warshallアルゴリズム*Dijkstraアルゴリズム*Bellman-Fordアルゴリズム
Floydアルゴリズム
Flooydアルゴリズムは、任意の結点からすべての結点までの最短経路を計算することができ、その時間の複雑さは次の通りである.
O(n 3)O(n 3)
コード
データ構造図論の最短パスアルゴリズムは、古典的な3つがあります.*Floyd Warshallアルゴリズム*Dijkstraアルゴリズム*Bellman-Fordアルゴリズム
Floydアルゴリズム
Flooydアルゴリズムは、任意の結点からすべての結点までの最短経路を計算することができ、その時間の複雑さは次の通りである.
O(n 3)O(n 3)
コード
void InitializeDistanceMatrix(Directed_Weighted_Graph *G);
for(int k = 0; k < n; k++) {
for(int i = 0; i < n; i++) {
if(D[i][j] > D[i][k] + D[k][j])
D[i][j] = D[i][k] + D[k][j];
}
}