플로이드 와샬 알고리즘

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

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

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

기본 초기화 방법

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 <iostream>
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

 

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