플로이드-와샬 알고리즘: Difference between revisions
From IT위키
(새 문서: 분류:알고리즘 ;Floyd-Warshall Algorithm ;전체쌍(All-pair) 최단경로 알고리즘 == 의사 코드 == <pre> Shortest(A, C) { for(i=1; i<=n; i++) do for(j=1;...) |
No edit summary |
||
| Line 9: | Line 9: | ||
for(i=1; i<=n; i++) | for(i=1; i<=n; i++) | ||
do for(j=1; j<=n; j++) | do for(j=1; j<=n; j++) | ||
do A[i, j] = C[i, j]; | do A[i,j] = C[i,j]; | ||
P[i,j] = 0; | P[i,j] = 0; | ||
for(i=1; i<=n; i++) | for(i=1; i<=n; i++) | ||
| Line 16: | Line 16: | ||
do for(i=1; i<=n; i++) | do for(i=1; i<=n; i++) | ||
do for(j=1; j<=n; j++) | do for(j=1; j<=n; j++) | ||
if A[i, j] > A[i, k] + A[k, j] | if A[i,j] > A[i,k] + A[k,j] | ||
A[i, j] = A[i, k] + A[k, j] | A[i,j] = A[i,k] + A[k,j] | ||
P[i, j] = k; | P[i,j] = k; | ||
} | } | ||
</pre> | </pre> | ||
Latest revision as of 17:48, 12 February 2021
- Floyd-Warshall Algorithm
- 전체쌍(All-pair) 최단경로 알고리즘
의사 코드[edit | edit source]
Shortest(A, C)
{
for(i=1; i<=n; i++)
do for(j=1; j<=n; j++)
do A[i,j] = C[i,j];
P[i,j] = 0;
for(i=1; i<=n; i++)
do A[i,i] = 0;
for(k=1; k<=n; k++)
do for(i=1; i<=n; i++)
do for(j=1; j<=n; j++)
if A[i,j] > A[i,k] + A[k,j]
A[i,j] = A[i,k] + A[k,j]
P[i,j] = k;
}
