플로이드 와샬 알고리즘 : 모든 정점에서 모든 정점으로의 최단 경로를 구하는 알고리즘.
<전체적인 알고리즘>
1. 시작점에서 목적지로 가는 경로에 한 정점을 지나갈 때 거리가 더 짧아지면 해당 경로로 갱신한다.
2. 모든 시작점과 모든 목적지 쌍에 대해 1을 반복한다.
<시간 복잡도>
당연히 O(n^3)이다. 그냥 코드만 봐도 3중첩 for문이다.
<경로 구하는 알고리즘>
갱신될 때 마다 지나야 하는 k를 저장해두면 되돌아가면서 경로를 찾을 수 있다.
<전체 코드>
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 | #include<iostream>using namespace std;int INF = 987654321;int PAD = 0;int dist[6][6] = // 그래프 셋팅 //직관적이기 쉽게 index0은 패딩으로 채움{ {PAD,PAD,PAD,PAD,PAD,PAD}, {PAD,0,6,8,INF,2}, {PAD, INF,0,INF,5,INF}, {PAD ,4,INF,0,INF,1}, {PAD ,11,INF,INF,0,INF}, {PAD ,INF,INF,INF,3,0}};int n = 5;int P[5][5];void Floyd(){ for (int k = 1; k <= n; k++) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (dist[i][j] > dist[i][k] + dist[k][j]) //k노드를 거치는게 빠르면 갱신 { dist[i][j] = dist[i][k] + dist[k][j]; P[i][j] = k; //i에서j로 가는 최단경로 갱신되는 k노드 저장. } } } }}void path(int start, int end){ if (P[start][end] == 0)return; path(start, P[start][end]); cout << P[start][end] << " "; path(P[start][end], end);}void PATH(int start, int end){ cout << start << " "; path(start, end); cout << end << " ";}int main(){ Floyd(); for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (i != j) { printf("%d -> %d 최단 거리 : %2d", i, j, dist[i][j]); printf(" 최단 경로 : "); PATH(i, j); // i 에서 j로 가는 최단 경로 printf("\n"); } } } return 0;} |
궁금하신 점은 댓글에 남겨주시면 답변드리겠습니다.
반응형