최단경로 알고리즘
에지에 가중치가 주어진 방향 그래프에서 경로의 길이는 경로 상에 있는 에지 가중치 합이다.
이 합이 가장 작을 때 ‘최단 경로’라고 한다.
벨만 포드 알고리즘
음수 사이클이 없다고 가정한 단일-소스 최단 경로 알고리즘, 매 반복마다 모든 에지를 조사해 나가며 소스와의 최단 거리를 구하는 알고리즘
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; }
2 thoughts on “Data Structure – Bellman Ford Algorithm”
Everything is very open with a really clear clarification of
the issues. It was definitely informative.
Your site is extremely helpful. Thanks for sharing!
Hi Dear, are you truly visiting this site on a regular basis, if so
afterward you will absolutely take fastidious knowledge.