[Algorithm] [C++] 플로이드 와샬 알고리즘 (Floyd-Warshall)
다익스트라 알고리즘 / 플로이드 와샬 알고리즘
다익스트라 알고리즘
: 출발지 정점을 하나 정해놓고 그곳에서부터 다른 모든 정점으로의 최단 경로를 구함.
가장 적은 비용을 하나씩 선택해감 (우선순위 큐)
플로이드 와샬 알고리즘
: 모든 정점에서 모든 정점으로의 최단 경로를 한번에 구함. 즉, 정점과 정점, 모든 쌍의 최단 경로를 구함.
모든 쌍을 표현하는 행렬(이차원 배열)을 선언하고 다이나믹 프로그래밍 방식으로 각 쌍의 최단 거리를 업데이트. (업데이트 기준: 현재 거치는 정점)
거쳐가는 정점을 기준으로 알고리즘 수행. (i->j로 가는 경우 해당 정점을 경유해 가는 것이 빠르다면 그 정점을 거쳐가는 경로로 업데이트)
점화식: distance[i,j] = min(distance[i,j], distance[i,n] + distance[n,j]);
i에서 정점 n을 거쳐 j로 갈 때 n을 거쳐 가는 것이 더 최단 경로이면 업데이트.
코드
int INF = 1000000;
int a[4][4] = {
{ 0, 5, INF, 8 },
{ 7, 0, 9, INF },
{ 2, INF, 0, 4 },
{ INF, INF, 3, 0 }
};
// 시간복잡도 V^3
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 (a[i][k] + a[k][j] < a[i][j]) {
// 점화식
// distance[i,j] = min(distance[i,j],distance[i,n]+distance[n,j])
a[i][j] = a[i][k] a[k][j];
}
}
}
}
Author And Source
이 문제에 관하여([Algorithm] [C++] 플로이드 와샬 알고리즘 (Floyd-Warshall)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@dbsrud11/Algorithm-C-플로이드-와샬-알고리즘-Floyd-Warshall저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)