최단경로 알고리즘

에지에 가중치가 주어진 방향 그래프에서 경로의 길이는 경로 상에 있는 에지 가중치 합이다.
이 합이 가장 작을 때 ‘최단 경로’라고 한다.

플로이드 알고리즘

모든 정점간의 최단 경로를 구하는 알고리즘, 음수 사이클이 없다고 가정

시간복잡도: O(n^3), n은 정점의 개수

그래프 예시

플로이드 알고리즘 구현

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

#define TRUE 1
#define FALSE 0
#define MAX_VERTICS 100
#define INF 1000000

typedef struct GraphType {
	int n;
	int weight[MAX_VERTICS][MAX_VERTICS];
}GraphType;

int A[MAX_VERTICS][MAX_VERTICS];

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

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

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

int main(void) {
	GraphType g = {
		8,{
		{0,INF,INF,INF,INF,INF,INF,INF},
		{300,0,INF,INF,INF,INF,INF,INF},
		{1000,800,0,INF,INF,INF,INF,INF},
		{INF,INF,1200,0,INF,INF,INF,INF},
		{INF,INF,INF,1500,0,250,INF,INF},
		{INF,INF,INF,1000,INF,0,900,1400},
		{INF,INF,INF,INF,INF,INF,0,1000},
		{1700,INF,INF,INF,INF,INF,INF,0}
		}
	};
	floyd(&g);
	return 0;
}