최단 경로 알고리즘 (다익스트라, 벨만-포드)

최단 경로 알고리즘은 그래프에서 두 정점 간의 최단 경로를 찾는 문제를 해결하기 위한 알고리즘입니다. 이 글에서는 가장 널리 알려진 두 가지 최단 경로 알고리즘인 다익스트라 알고리즘과 벨만-포드 알고리즘에 대해 설명하고, 각 알고리즘의 구현을 Java와 C 언어로 제공하겠습니다.

다익스트라 알고리즘

다익스트라 알고리즘은 양의 가중치를 가진 그래프에서 한 정점으로부터 다른 모든 정점까지의 최단 경로를 찾는 데 사용됩니다. 다익스트라 알고리즘은 그리디 알고리즘의 한 종류로, 최단 경로를 점진적으로 확장해 나가는 방식으로 작동합니다. 이 알고리즘은 우선순위 큐를 사용하여 가장 비용이 적은 정점을 선택해 나가며 최단 경로를 찾습니다.

다익스트라 알고리즘의 특징

• 시간 복잡도: 우선순위 큐(힙)를 사용하면 O((V + E) log V)의 시간 복잡도를 가집니다. 여기서 V는 정점의 수, E는 간선의 수입니다.
• 음수 가중치를 가지는 그래프에서는 사용할 수 없습니다.

Java로 구현한 다익스트라 알고리즘

import java.util.*;

class Dijkstra {
    static class Node implements Comparable<Node> {
        int vertex, weight;

        Node(int vertex, int weight) {
            this.vertex = vertex;
            this.weight = weight;
        }

        public int compareTo(Node other) {
            return Integer.compare(this.weight, other.weight);
        }
    }

    public static void dijkstra(int start, List<List<Node>> graph) {
        int V = graph.size();
        int[] dist = new int[V];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;

        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(start, 0));

        while (!pq.isEmpty()) {
            Node current = pq.poll();
            int u = current.vertex;

            for (Node neighbor : graph.get(u)) {
                int v = neighbor.vertex;
                int weight = neighbor.weight;

                if (dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                    pq.add(new Node(v, dist[v]));
                }
            }
        }

        // 최단 경로 출력
        for (int i = 0; i < V; i++) {
            System.out.println("Vertex " + i + ", Distance: " + dist[i]);
        }
    }

    public static void main(String[] args) {
        int V = 5;
        List<List<Node>> graph = new ArrayList<>();

        for (int i = 0; i < V; i++) {
            graph.add(new ArrayList<>());
        }

        // 그래프 초기화
        graph.get(0).add(new Node(1, 10));
        graph.get(0).add(new Node(4, 5));
        graph.get(1).add(new Node(2, 1));
        graph.get(4).add(new Node(1, 3));
        graph.get(4).add(new Node(2, 9));
        graph.get(2).add(new Node(3, 4));

        dijkstra(0, graph);
    }
}

C로 구현한 다익스트라 알고리즘

#include <stdio.h>
#include <limits.h>
#define V 5

int minDistance(int dist[], int sptSet[]) {
    int min = INT_MAX, min_index;

    for (int v = 0; v < V; v++)
        if (sptSet[v] == 0 && dist[v] <= min)
            min = dist[v], min_index = v;

    return min_index;
}

void dijkstra(int graph[V][V], int src) {
    int dist[V];
    int sptSet[V] = {0};

    for (int i = 0; i < V; i++)
        dist[i] = INT_MAX;
    dist[src] = 0;

    for (int count = 0; count < V - 1; count++) {
        int u = minDistance(dist, sptSet);
        sptSet[u] = 1;

        for (int v = 0; v < V; v++)
            if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v])
                dist[v] = dist[u] + graph[u][v];
    }

    for (int i = 0; i < V; i++)
        printf("Vertex %d, Distance: %d\n", i, dist[i]);
}

int main() {
    int graph[V][V] = {
        {0, 10, 0, 0, 5},
        {0, 0, 1, 0, 2},
        {0, 0, 0, 4, 0},
        {0, 0, 0, 0, 0},
        {0, 3, 9, 2, 0}
    };

    dijkstra(graph, 0);
    return 0;
}

벨만-포드 알고리즘

벨만-포드 알고리즘은 음의 가중치를 가진 그래프에서도 사용할 수 있는 최단 경로 알고리즘입니다. 벨만-포드 알고리즘은 출발 정점으로부터 다른 모든 정점까지의 최단 경로를 찾습니다. 이 알고리즘은 간선을 반복적으로 완화(Relaxation)하여 최단 경로를 찾습니다.

벨만-포드 알고리즘의 특징

• 시간 복잡도: O(V * E). 여기서 V는 정점의 수, E는 간선의 수입니다.
• 음수 사이클이 있는 경우 이를 감지할 수 있습니다.

Java로 구현한 벨만-포드 알고리즘

import java.util.*;

class BellmanFord {
    static class Edge {
        int src, dest, weight;

        Edge(int src, int dest, int weight) {
            this.src = src;
            this.dest = dest;
            this.weight = weight;
        }
    }

    public static void bellmanFord(int V, List<Edge> edges, int start) {
        int[] dist = new int[V];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;

        for (int i = 1; i < V; i++) {
            for (Edge edge : edges) {
                if (dist[edge.src] != Integer.MAX_VALUE && dist[edge.src] + edge.weight < dist[edge.dest]) {
                    dist[edge.dest] = dist[edge.src] + edge.weight;
                }
            }
        }

        // 음수 사이클 체크
        for (Edge edge : edges) {
            if (dist[edge.src] != Integer.MAX_VALUE && dist[edge.src] + edge.weight < dist[edge.dest]) {
                System.out.println("Graph contains negative weight cycle");
                return;
            }
        }

        // 최단 경로 출력
        for (int i = 0; i < V; i++) {
            System.out.println("Vertex " + i + ", Distance: " + dist[i]);
        }
    }

    public static void main(String[] args) {
        int V = 5;
        List<Edge> edges = new ArrayList<>();

        edges.add(new Edge(0, 1, 10));
        edges.add(new Edge(0, 4, 5));
        edges.add(new Edge(1, 2, 1));
        edges.add(new Edge(4, 1, 3));
        edges.add(new Edge(4, 2, 9));
        edges.add(new Edge(2, 3, 4));

        bellmanFord(V, edges, 0);
    }
}

C로 구현한 벨만-포드 알고리즘

#include <stdio.h>
#include <limits.h>
#define V 5
#define E 7

struct Edge {
    int src, dest, weight;
};

void bellmanFord(struct Edge edges[], int src) {
    int dist[V];
    for (int i = 0; i < V; i++)
        dist[i] = INT_MAX;
    dist[src] = 0;

    for (int i = 1; i < V; 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] != INT_MAX && dist[u] + weight < dist[v])
                dist[v] = dist[u] + weight;
        }
    }

    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] != INT_MAX && dist[u] + weight < dist[v]) {
            printf("Graph contains negative weight cycle\n");
            return;
        }
    }

    for (int i = 0; i < V; i++)
        printf("Vertex %d, Distance: %d\n", i, dist[i]);
}

int main() {
    struct Edge edges[E] = {
        {0, 1, 10}, {0, 4, 5}, {1, 2, 1}, {4, 1, 3}, {4, 2, 9}, {2, 3, 4}, {3, 4, 7}
    };

    bellmanFord(edges, 0);
    return 0;
}

결론

다익스트라와 벨만-포드 알고리즘은 그래프에서 최단 경로를 찾기 위한 대표적인 알고리즘입니다. 다익스트라는 양의 가중치를 가진 그래프에서 효율적으로 동작하며, 벨만-포드는 음수 가중치를 허용하고 음수 사이클을 감지할 수 있는 장점이 있습니다. 문제의 조건에 따라 적절한 알고리즘을 선택하여 사용하면 됩니다.