플로이드-와샬 알고리즘: 두 판 사이의 차이
IT위키
(새 문서: 분류:알고리즘 ;Floyd-Warshall Algorithm ;전체쌍(All-pair) 최단경로 알고리즘 == 의사 코드 == <pre> Shortest(A, C) { for(i=1; i<=n; i++) do for(j=1;...) |
편집 요약 없음 |
||
| 9번째 줄: | 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++) | ||
| 16번째 줄: | 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> | ||
2021년 2월 12일 (금) 17:48 기준 최신판
- Floyd-Warshall Algorithm
- 전체쌍(All-pair) 최단경로 알고리즘
의사 코드[편집 | 원본 편집]
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;
}
