그래프는 정점과 간선의 집합으로 이루어진 자료 구조입니다. 그래프의 최단 경로 알고리즘은 한 정점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘입니다. 이번 글에서는 다익스트라 알고리즘과 벨만-포드 알고리즘에 대해 알아보겠습니다.

다익스트라 알고리즘

다익스트라 알고리즘은 너비 우선 탐색을 이용하여 가중치가 있는 그래프에서 최단 경로를 찾는 알고리즘입니다. 이 알고리즘은 시작 정점으로부터 각 정점까지의 최단 거리를 저장하면서 탐색을 진행합니다.

#include <stdio.h>
#define INF 9999

void dijkstra(int graph[V][V], int src) {
    int dist[V];
    for (int i = 0; i < V; i++)
        dist[i] = INF;
    dist[src] = 0;
    // 다익스트라 알고리즘 구현
}

다익스트라 알고리즘은 우선순위 큐를 사용하여 효율적으로 구현할 수 있습니다. 이를 통해 O(E log V)의 시간 복잡도를 가집니다.

벨만-포드 알고리즘

벨만-포드 알고리즘은 음수 가중치가 있는 그래프에서도 동작하는 최단 경로 알고리즘입니다. 이 알고리즘은 간선을 모든 정점의 수 - 1 번 순회하여 최단 거리를 갱신합니다.

#include <stdio.h>
#define INF 9999

void bellmanFord(int graph[V][V], int src) {
    int dist[V];
    for (int i = 0; i < V; i++)
        dist[i] = INF;
    dist[src] = 0;
    // 벨만-포드 알고리즘 구현
}

벨만-포드 알고리즘은 시간 복잡도 O(V*E)를 갖습니다. 이 알고리즘은 음수 사이클을 감지할 수 있는 장점이 있지만, 성능 면에서 다익스트라 알고리즘에 비해 느린 편입니다.

그래프의 최단 경로 알고리즘은 다양한 문제에 응용될 수 있는 중요한 알고리즘입니다. 위에서 다룬 알고리즘들을 적절히 활용하여 원하는 최단 경로를 찾을 수 있습니다.

참고 자료