최단경로 알고리즘

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

벨만 포드 알고리즘

음수 사이클이 없다고 가정한 단일-소스 최단 경로 알고리즘, 매 반복마다 모든 에지를 조사해 나가며 소스와의 최단 거리를 구하는 알고리즘

s-v의 최단 거리를 구하는데 만일 u점을 거쳐서 구했을 때가 더 작은 경우 업데이트한다.
이 때 u점은 여러 개가 존재할 수 있으므로 (s->u->v)의 가중치 합이 최소인 것으로 한다.

시간복잡도: O(nm), n은 정점의 개수, m은 에지의 개수

※ 위 이미지에서 (3)과정의 start와 end는 오류가 있음 -> 소스 참고해서 변경

벨만 포드 알고리즘 구현

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

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

typedef struct Edge {
	int start, end, weight;
}Edge;

typedef struct GraphType {
	int n, m; // 정점의 개수, 간선의 개수
	Edge* edge; // 에지 배열 
}GraphType;

int dist[MAX_VERTICS]; // distance: 해당 정점까지의 (현재) 최단 거리를 저장함 
int parent[MAX_VERTICS]; // 해당 정점을 거치기 전에 바로 지나는 정점 저장 

// 그래프 생성 후 반환 
GraphType* createGraph(int n, int m) {
	GraphType* g = (GraphType*)malloc(sizeof(GraphType));
	g->n = n;
	g->m = m;
	g->edge = (Edge*)malloc(sizeof(Edge) * m);
	return g;
}

// 그래프에 에지 정보 입력 
void makeEdge(GraphType* g, int start, int end, int weight) {
	static int num = 0;
	g->edge[num].start = start;
	g->edge[num].end = end;
	g->edge[num].weight = weight;
	num++;
}

// (s)~ 최단 경로 출력 
void print(GraphType* g) {
	static int r = 1;
	printf("\n = Round %d = ", r++);

	printf("\n distance: ");
	for (int i = 0; i < g->n; i++) {
		if (dist[i] != INF)
			printf("[%d] ", dist[i]);
		else
			printf("[INF] ");
	}
	printf("\n   parent: ");
	for (int i = 0; i < g->n; i++) {
		if (parent[i] != INF)
			printf("[%d] ", parent[i]);
		else
			printf("[INF] ");
	}
	printf("\n");
}

// 최단 경로 구하기 
void bellman(GraphType* g, int s) {
	for (int i = 0; i < g->n; i++)
		dist[i] = parent[i] = INF;
	dist[s] = 0;

	// n번 반복해서 구하기 
	 
	// n-1번째 라운드까지: dist배열 업데이트 하기 (최단거리 구하기)
	// n번째 라운드: 음수 사이클 찾기

	for (int i = 0; i < g->n; i++) {
		int count = 0;

		// 모든 에지에 대해서 구하기 
		for (int j = 0; j < g->m; j++) {
			int u = g->edge[j].start;
			int v = g->edge[j].end; // 도착점
			int weight = g->edge[j].weight;

			// u점까지의 최단 거리+가중치 < 도착점까지의 최단거리 => 업데이트 
			if (dist[u] != INF && dist[u] + weight < dist[v]) {
				// n번째 라운드에서도 값이 갱신된다면 음수 사이클이 존재 
				if (i == g->n - 1) {
					printf("Find Negative Cycle, when [%d->%d]\n", u, v);
					continue;
				}
				dist[v] = dist[u] + weight;
				parent[v] = u; // 최단 경로 트리의 부모 
			}
			// dist배열에 변화가 없으면 최단 경로를 이미 구함 
			else {
				if ((++count) == g->m)
					return;
			}
		}
		if (i < g->n - 1)
			print(g);
	}
}

int main(void) {
	// 음수 가중치가 포함된 방향 그래프 (음수 사이클 x) 
	GraphType* g = createGraph(6, 5);

	// 최악의 경우  
	makeEdge(g, 4, 5, -5);
	makeEdge(g, 3, 4, -4);
	makeEdge(g, 2, 3, -3);
	makeEdge(g, 1, 2, -2);
	makeEdge(g, 0, 1, -1);

	/*// 최선의 경우
	makeEdge(g, 0, 1, -1);
	makeEdge(g, 1, 2, -2);
	makeEdge(g, 2, 3, -3);
	makeEdge(g, 3, 4, -4);
	makeEdge(g, 4, 5, -5);*/


	/*// 음수 가중치가 포함된 방향 그래프 (음수 사이클 o)
	GraphType* g = createGraph(6, 6);
	// 최악의 경우
	makeEdge(g, 5, 4, -6);
	makeEdge(g, 4, 5, -5);
	makeEdge(g, 3, 4, -4);
	makeEdge(g, 2, 3, -3);
	makeEdge(g, 1, 2, -2);
	makeEdge(g, 0, 1, -1);*/


	bellman(g, 0);
	return 0;
}