[Data Structure] 최단 경로 - Floyd Algorithm

Floyd Algorithm

- 모든 정점 사이의 최단 경로

 

- Dijkstra : 정점의 수 n개 만큼 반복 실행

- Floyd : 한 번에 찾아 준다

 

- 인접 행렬 weight[][] 2차원 배열에 대한 3중 반복 루프 

- O(n³)

 

1. A^k[i][j]를 0~k까지의 정점만을 이용한 정점 i~j까지의 최단경로
2. 원하는 최종 결론 : A^n-1[i][j]
3. A^-1 → A⁰ → A¹ → ..... → A^n-1순으로 최단거리 구하기

 

 

▶ Floyd Algorithm Code

int A[MAX_VERTEX][MAX_VERTEX];

void floyd(graph* g) {
	for (int i = 0; i < g->n; i++) {
		for (int j = 0; j < g->n; j++) {
			A[i][j] = g->weight[i][j];
		}
	}
	print_floyd(g);

	for (int i = 0; i < g->n; i++) {
		for (int j = 0; j < g->n; j++)
			for (int k = 0; k < g->n; k++)
				if (A[j][k] > A[j][i] + A[i][k])
					A[j][k] = A[j][i] + A[i][k];
		print_floyd(g);
	}
}

void print_floyd(graph* g) {
	for (int i = 0; i < g->n; i++)
		printf("=====");
	printf("\n");
	for (int i = 0; i < g->n; i++) {
		for (int j = 0; j < g->n; j++) {
			if (A[i][j] == INF)
				printf("  *  ");
			else
				printf("%3d  ", A[i][j]);
		}
		printf("\n");
	}
	for (int i = 0; i < g->n; i++)
		printf("=====");
	printf("\n");
}

 

 

▶ Full Code

#include <stdio.h>
#include <stdlib.h>

// Floyd ShortestWay Algorithm
#define TRUE 1
#define FALSE 0
#define MAX_VERTEX 100
#define INF 99999

typedef struct graph {
	int n; // 정점 개수
	int vertex[MAX_VERTEX];
	int weight[MAX_VERTEX][MAX_VERTEX];
}graph;

int A[MAX_VERTEX][MAX_VERTEX];

graph* create() {
	return (graph*)malloc(sizeof(graph));
}

void init_graph(graph* g) {
	g->n = 0;
	for (int r = 0; r < MAX_VERTEX; r++) {
		for (int c = 0; c < MAX_VERTEX; c++) {
			g->weight[r][c] = INF;
		}
	}
}

int is_full(graph* g) {
	return g->n == MAX_VERTEX;
}

int bool_vertex(graph* g, int v) {
	int flag = FALSE;
	for (int i = 0; i < g->n; i++) {
		if (g->vertex[i] == v)
			flag = TRUE;
	}
	if (flag == TRUE) return TRUE;
	else return FALSE;
}

void insert_vertex(graph* g, int v) {
	if (is_full(g))
		return;
	else if (bool_vertex(g, v) == TRUE)
		return;
	g->vertex[g->n++] = v;
}

void insert_edge(graph* g, int start, int end, int weight) {
	// 무방향 그래프를 조건으로
	if (bool_vertex(g, start) == FALSE || bool_vertex(g, end) == FALSE)
		return;
	g->weight[start][end] = weight;
	g->weight[end][start] = weight;
}

void print_floyd(graph* g) {
	for (int i = 0; i < g->n; i++)
		printf("=====");
	printf("\n");
	for (int i = 0; i < g->n; i++) {
		for (int j = 0; j < g->n; j++) {
			if (A[i][j] == INF)
				printf("  *  ");
			else
				printf("%3d  ", A[i][j]);
		}
		printf("\n");
	}
	for (int i = 0; i < g->n; i++)
		printf("=====");
	printf("\n");
}

void floyd(graph* g) {
	for (int i = 0; i < g->n; i++) {
		for (int j = 0; j < g->n; j++) {
			A[i][j] = g->weight[i][j];
		}
	}
	print_floyd(g);

	for (int i = 0; i < g->n; i++) {
		for (int j = 0; j < g->n; j++)
			for (int k = 0; k < g->n; k++)
				if (A[j][k] > A[j][i] + A[i][k])
					A[j][k] = A[j][i] + A[i][k];
		print_floyd(g);
	}
}

int main(void) {
	graph* g;
	g = create(); init_graph(g);

	for (int i = 0; i < 7; i++)
		insert_vertex(g, i);
	insert_edge(g, 0, 1, 15);
	insert_edge(g, 0, 3, 54);
	insert_edge(g, 0, 4, 24);
	insert_edge(g, 1, 3, 37);
	insert_edge(g, 1, 4, 77);
	insert_edge(g, 1, 6, 43);
	insert_edge(g, 2, 4, 62);
	insert_edge(g, 2, 5, 17);
	insert_edge(g, 2, 6, 45);
	insert_edge(g, 3, 6, 31);
	insert_edge(g, 4, 5, 19);

	printf("-----------------------------------\n");
	printf("Floyd Algorithm\n");
	printf("-----------------------------------\n");
	floyd(g);

	return 0;
}