1. 최단 경로 문제 정의
- 방향 가중 그래프: 간선에 가중치가 있는 그래프.
- 경로 길이: 경로 상의 모든 간선의 가중치 합.
- 시작 정점: 경로가 시작되는 정점.
- 종료 정점: 경로가 끝나는 정점.
2. 최단 경로 유형
- 단일 출발점, 단일 도착점 (Single Source Single Destination): 특정 시작점에서 특정 도착점까지의 최단 경로를 찾기.
- 단일 출발점, 모든 도착점 (Single Source All Destinations): 특정 시작점에서 모든 정점까지의 최단 경로를 찾기.
- 모든 출발점, 모든 도착점 (All Pairs): 모든 정점 쌍 간의 최단 경로를 찾기.
3. 단일 출발점, 단일 도착점
- 가능한 알고리즘:
- 가장 저렴한 간선을 사용하여 시작 정점에서 출발.
- 새로운 정점에 도달할 때마다 가장 저렴한 간선을 사용하여 계속 진행.
- 도착 정점에 도달할 때까지 반복.
4. 다익스트라 알고리즘 (Dijkstra's Algorithm)
- 목적: 단일 출발점에서 모든 정점까지의 최단 경로를 찾기.
- 조건: 모든 간선의 가중치가 0 이상.
- 시간 복잡도:
- 인접 행렬 사용 시: O(n^2)
- 인접 리스트 사용 시: O(n + e log n) (e는 간선의 수)
#include <stdio.h>
#include <stdbool.h>
#include <limits.h>
#define MAX 100
#define INF INT_MAX
int graph[MAX][MAX];
int dist[MAX];
bool visited[MAX];
int n; // 정점의 개수
int minDistance() {
int min = INF, min_index;
for (int v = 0; v < n; v++)
if (!visited[v] && dist[v] <= min)
min = dist[v], min_index = v;
return min_index;
}
void dijkstra(int src) {
for (int i = 0; i < n; i++)
dist[i] = INF, visited[i] = false;
dist[src] = 0;
for (int count = 0; count < n - 1; count++) {
int u = minDistance();
visited[u] = true;
for (int v = 0; v < n; v++)
if (!visited[v] && graph[u][v] && dist[u] != INF && dist[u] + graph[u][v] < dist[v])
dist[v] = dist[u] + graph[u][v];
}
printf("Vertex \t Distance from Source\n");
for (int i = 0; i < n; i++)
printf("%d \t\t %d\n", i, dist[i]);
}
int main() {
n = 9;
int graph[MAX][MAX] = {
{0, 4, 0, 0, 0, 0, 0, 8, 0},
{4, 0, 8, 0, 0, 0, 0, 11, 0},
{0, 8, 0, 7, 0, 4, 0, 0, 2},
{0, 0, 7, 0, 9, 14, 0, 0, 0},
{0, 0, 0, 9, 0, 10, 0, 0, 0},
{0, 0, 4, 14, 10, 0, 2, 0, 0},
{0, 0, 0, 0, 0, 2, 0, 1, 6},
{8, 11, 0, 0, 0, 0, 1, 0, 7},
{0, 0, 2, 0, 0, 0, 6, 7, 0}
};
dijkstra(0);
return 0;
}
5. 벨만-포드 알고리즘 (Bellman-Ford Algorithm)
- 목적: 단일 출발점에서 모든 정점까지의 최단 경로를 찾기.
- 조건: 간선 가중치가 음수일 수 있음.
- 시간 복잡도:
- 인접 행렬 사용 시: O(n^3)
- 인접 리스트 사용 시: O(n * e)
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define MAX 100
#define INF INT_MAX
typedef struct {
int src, dest, weight;
} Edge;
Edge edges[MAX];
int dist[MAX];
int n, e; // 정점과 간선의 수
void bellmanFord(int src) {
for (int i = 0; i < n; i++)
dist[i] = INF;
dist[src] = 0;
for (int i = 1; i <= n - 1; i++) {
for (int j = 0; j < e; j++) {
int u = edges[j].src;
int v = edges[j].dest;
int weight = edges[j].weight;
if (dist[u] != INF && dist[u] + weight < dist[v])
dist[v] = dist[u] + weight;
}
}
for (int i = 0; i < e; i++) {
int u = edges[i].src;
int v = edges[i].dest;
int weight = edges[i].weight;
if (dist[u] != INF && dist[u] + weight < dist[v])
printf("Graph contains negative weight cycle\n");
}
printf("Vertex \t Distance from Source\n");
for (int i = 0; i < n; i++)
printf("%d \t\t %d\n", i, dist[i]);
}
int main() {
n = 5;
e = 8;
Edge inputEdges[] = {
{0, 1, -1}, {0, 2, 4},
{1, 2, 3}, {1, 3, 2},
{1, 4, 2}, {3, 2, 5},
{3, 1, 1}, {4, 3, -3}
};
for (int i = 0; i < e; i++)
edges[i] = inputEdges[i];
bellmanFord(0);
return 0;
}
6. 플로이드-와샬 알고리즘 (Floyd-Warshall Algorithm)
- 목적: 모든 정점 쌍 간의 최단 경로를 찾기.
- 조건: 간선 가중치가 음수일 수 있으나 음수 사이클은 없음.
- 시간 복잡도: O(n^3)
#include <stdio.h>
#include <limits.h>
#define MAX 100
#define INF INT_MAX
int graph[MAX][MAX];
int dist[MAX][MAX];
int n; // 정점의 수
void floydWarshall() {
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
dist[i][j] = graph[i][j];
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (dist[i][k] != INF && dist[k][j] != INF && dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
printf("Shortest distances between every pair of vertices:\n");
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (dist[i][j] == INF)
printf("%7s", "INF");
else
printf("%7d", dist[i][j]);
}
printf("\n");
}
}
int main() {
n = 4;
int graph[MAX][MAX] = {
{0, 5, INF, 10},
{INF, 0, 3, INF},
{INF, INF, 0, 1},
{INF, INF, INF, 0}
};
floydWarshall();
return 0;
}
요약
- 다익스트라 알고리즘: 단일 출발점에서 모든 정점까지의 최단 경로를 찾는 알고리즘. 간선 가중치가 0 이상이어야 함.
- 벨만-포드 알고리즘: 단일 출발점에서 모든 정점까지의 최단 경로를 찾는 알고리즘. 간선 가중치가 음수일 수 있음.
- 플로이드-와샬 알고리즘: 모든 정점 쌍 간의 최단 경로를 찾는 알고리즘. 간선 가중치가 음수일 수 있으나 음수 사이클은 없음.
Comments 0