[기본문제풀이] floydwarshall

풀이 일시 : 2020-08-13

​

플로이드와샬 알고리즘 :

그래프 정점간 최단거리를 구하는 알고리즘 중 모든 최단 경로를 구하는 방법이다. (다익스트라는 한 점에서 다른점까지의 최단 경로) 또한 플로이드와샬에서는 음의 가중치를 가진 간선을 사용할 수 있다.

모든 정점에 대한 경로를 계산하므로 거리를 저장할 자료구조는 2차원 배열이 된다.

​

문제 :

주어진 인접행렬에서 플로이드 와샬 알고리즘을 사용하여 모든 거리를 구하라

{0 , 5 , inf , 8},

{7 , 0 , 9 , inf},

{2 , inf , 0 , 4},

{inf , inf , 3 , 0}

 

풀이 : 

#include <stdio.h>

int number = 4;
int inf = 10000000;

int a[4][4] = {
{0,5,inf,8},
{7,0,9,inf},
{2,inf,0,4},
{inf,inf,3,0}
};

void floydWarshall() {
	int d[4][4];

	//그래프를 초기화한다.
	for (int i = 0; i < number; i++) {
		for (int j = 0; j < number; j++) {
			d[i][j] = a[i][j];
		}
	}

	for (int k = 0; k < number; k++) { //0 1 2 3
		for (int i = 0; i < number; i++) {
			for (int j = 0; j < number; j++) {
				if (d[i][k] + d[k][j] < d[i][j]) { //k를 거쳐가는경우를 따져준다.
					d[i][j] = d[i][k] + d[k][j];
				}
			}
		}
	}

	//출력
	for (int i = 0; i < number; i++) {
		for (int j = 0; j < number; j++) {
			printf("%3d ", d[i][j]);
		}
		printf("\n");
	}
}

int main() {
	floydWarshall();
}