Floyd Washall Algorithm(플로이드 와샬 알고리즘)

1.플로이드 와샬 알고리즘

: 모든 정점에서 모든 정점으로의 최단 경로를 구하는 알고리즘

:2차원 배열 이용하여 계속적으로 비용 업데이트

cf> 다익스트라(Dijkstra Alogrithm)

:한 정점에서 출발했을 때 다른 모든 정점으로의 최단 경로

:1차원 배열 이용

#include <stdio.h>
#define INF 100000

void Floyd_Washall(int(*g)[4], int size) {
	int cost[4][4] = { 0 };
	int i, j,k;
	for (i = 0; i < size; i++) {
		for (j = 0; j < size; j++) {
			cost[i][j] = g[i][j];
		}
	}

	for (i = 0; i < size; i++) {
		for (j = 0; j < size; j++) {
			for (k = 0; k < size; k++) {
				if (j != i && k != i) {
					if (cost[j][k] > cost[j][i] + cost[i][k]) {
						cost[j][k] = cost[j][i] + cost[i][k];
					}
				}
			}
		}
	}

	for (i = 0; i < size; i++) {
		for (j = 0; j < size; j++) {
			printf("%3d ", cost[i][j]);
		}
		printf("\n");
	}
}

int main() {

	int graph[4][4] = { {0,5,INF,8},{7,0,9,INF},
		{2,INF,0,4},{INF,INF,3,0} };
	int size = sizeof(graph) / sizeof(graph[0]);

	Floyd_Washall(graph, size);





	getchar();
	return 0;
}