플로이드 와샬 알고리즘

플로이드 와샬 알고리즘

모든 노드에서 모든 노드의 최단 경로를 구할 때 사용

양의 가중치와 음의 가중치 모두 사용 가능

하지만 음의 가중치 일 경우 사이클이 없어야함.

기본 초기화 방법

V : 정점의 개수

E : 간선의 개수

arr[i][j] : i에서 j로 가는 비용

int V, E; int arr[101][101]; int a, b, c; cin >> V >> E; for (int i = 0; i < E; i++) { cin >> a >> b >> c; // a에서 b로 다닐수 있는 비용 c인 길 arr[a][b] = c; arr[b][a] = c; }

이렇게 처음에 정점의 개수와 간선의 개수를 입력받고

간서의 개수만큼 a b c 를 입력 받는다( a에서 b로 다닐 수 있는 비용 c인 길 )

위의 코드는 양방향으로 길을 놓아주는 것인데

단방향으로 원하는 경우 ( a에서 b로 다니는 비용 c인 길 )

아래의 코드처럼 그냥 arr[b][a]=c; 를 빼주면 된다.

int a, b, c; cin >> V >> E; for (int i = 0; i < E; i++) { cin >> a >> b >> c; arr[a][b] = c; }

i에서 j로 갈 때 비용이 0이면 갈 수 없는 길이므로 987654321( INF : 무한 )으로 그냥 큰 수로 초기화시켜준다.

아래의 코드를 제외해서 987654321로 굳이 안 바꿔주어도 못 가는 길의 비용은 0으로 보면 된다.

for(int i=1;i<=V;i++) for (int j = 1; j <= V; j++) { if (arr[i][j] == 0) arr[i][j] = 987654321; }

플로이드 와샬의 핵심 부분

for (int k = 1; k <= V; k++) // 중간에 거칠 노드 K for (int i = 1; i <= V; i++) // i노드에서 출발 for (int j = 1; j <= V; j++) // j노드에 도착 if (i!=j&&arr;[i][j] > arr[i][k] + arr[k][j])// i!=j시작과 도착지가 다르게 함 arr[i][j] = arr[i][k] + arr[k][j];

한 정점(k)을 거쳐 출발지(i)에서 도착지(j)로 가는 길을 최소비용으로 초기화시켜준다

arr[i][j]가 i에서 j로 가는 비용인데

이것이 arr[i][k] + arr[k][j] ( i에서 k를 도착하고, k에서 j로 가는 비용 ) 보다 크면

k를 거쳐가는 방법 arr[i][k] + arr[k][j]가 더 쌀 테니 이 방법을 arr[i][j], i를 거쳐 j로 가는 최단 비용으로 초기화 시켜준다.

전체 코드 및 실행 결과

#include using namespace std; int V, E; int arr[101][101]; int main(void) { int a, b, c; cin >> V >> E; for (int i = 0; i < E; i++) { cin >> a >> b >> c; arr[a][b] = c; arr[b][a] = c; } for(int i=1;i<=V;i++) for (int j = 1; j <= V; j++) { if (arr[i][j] == 0) arr[i][j] = 987654321; } for (int k = 1; k <= V; k++) for (int i = 1; i <= V; i++) for (int j = 1; j <= V; j++) if (i!=j&&arr;[i][j] > arr[i][k] + arr[k][j]) arr[i][j] = arr[i][k] + arr[k][j]; cout << endl; // 실행 결과를 확인을 위한 코드 for (int k = 1; k <= V; k++) { for (int i = 1; i <= V; i++) cout << arr[k][i] << " "; cout << endl; } }

위의 그래프를 예로 입출력을 확인해 보겠습니다.

입력

5 7 ( 5개의 정점 7개의 간선 )

1 2 3 ( 7개의 간선의 정보를 입력, a에서 b로 가는 비용 c )

1 3 4

1 4 5

2 3 8

2 4 5

4 5 6

5 3 2

출력

987654321 3 4 5 6

3 987654321 7 5 9

4 7 987654321 8 2

5 5 8 987654321 6

6 9 2 6 987654321

존재하지 않는 길은 987654321(무한)으로 나타내었습니다.

정점 1에서 1로 가는 최단 비용 : 987654321 ( 길이 없음 ) <<< 처음 초기화 때 987654321로 안 했으면 0이 출력

정점 1에서 2로 가는 최단 비용 : 1->2로 비용 3

정점 1에서 3로 가는 최단 비용 : 1->3로 비용 4

정점 1에서 4로 가는 최단 비용 : 1->4로 비용 5

정점 1에서 5로 가는 최단 비용 : 1->3->5로 비용 6

모든 정점에서 모든 정점으로 가는 최단 비용이 잘 저장되었습니다.

from http://non-stop.tistory.com/20 by ccl(A) rewrite - 2021-12-24 18:01:09