[グラフ]Floyd-Warshall
Floyd-Warshall
すべての頂点からすべての異なる頂点までの最短距離を求めるアルゴリズム.
dijikstraは、1つの頂点から他のすべての頂点までの最短距離です.
負の重みのある幹線も処理できますが、ループがない限り
問題によって方法が違うので、よく知っておいたほうがいいです.
時間の複雑さ
O(n^3)サンプルコード
外複文(k):中間の頂点
中間反復文(i):出発の頂点
内反復文(j):到達頂点
計算済みの出発地から目的地までの道が真ん中を通る頂点よりも短い場合は、更新
const int INF = 0x7fffffff;
int matrix[4][4] = {
{ 0, 1, 3, 8 },
{ 7, 0, INF, INF },
{ 2, 2, 4, 4 },
{ 8, INF, 5, INF }
};
void floydWarshall(){
for(int k = 0; k < 4; k++) // k 는 거쳐가는 정점
for(int i = 0; i < 4; i++) // i 는 행 (출발 정점)
for(int j = 0; j < 4; j++) // j 는 열 (도착 정점)
if (matrix[i][k] + matrix[k][j] < matrix[i][j]) // 점화식 distance[i,j] = min(distance[i,j], distance[i,n] + distance[n,j])
matrix[i][j] = matrix[i][k] + matrix[k][j];
}Reference
この問題について([グラフ]Floyd-Warshall), 我々は、より多くの情報をここで見つけました https://velog.io/@rxjw95/그래프floyd-warshallテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol