[알고리즘] 다익스트라, 벨만-포드

출처 : https://namu.wiki/w/%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BC%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

다익스트라 알고리즘

가중치가 있는 그래프에서 한 정점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘. 음의 가중치가 없을 때 사용 가능하다.
자바 코드 예시:

import java.util.*;

public class Graph {
    private int numVertices;
    private LinkedList<Edge>[] adjList;

    private class Edge {
        int vertex;
        int weight;

        Edge(int v, int w) {
            vertex = v;
            weight = w;
        }
    }

    public Graph(int vertices) {
        numVertices = vertices;
        adjList = new LinkedList[vertices];
        for (int i = 0; i < vertices; i++) {
            adjList[i] = new LinkedList<>();
        }
    }

    public void addEdge(int src, int dest, int weight) {
        adjList[src].add(new Edge(dest, weight));
    }

    public void dijkstra(int startVertex) {
        int[] distances = new int[numVertices];
        boolean[] visited = new boolean[numVertices];
        Arrays.fill(distances, Integer.MAX_VALUE);
        distances[startVertex] = 0;
        PriorityQueue<Edge> pq = new PriorityQueue<>(Comparator.comparingInt(e -> e.weight));

        pq.add(new Edge(startVertex, 0));

        while (!pq.isEmpty()) {
            Edge current = pq.poll();
            if (visited[current.vertex]) continue;
            visited[current.vertex] = true;

            for (Edge e : adjList[current.vertex]) {
                if (!visited[e.vertex] && distances[current.vertex] + e.weight < distances[e.vertex]) {
                    distances[e.vertex] = distances[current.vertex] + e.weight;
                    pq.add(new Edge(e.vertex, distances[e.vertex]));
                }
            }
        }

        for (int i = 0; i < numVertices; i++) {
            System.out.println("Distance from " + startVertex + " to " + i + " is " + distances[i]);
        }
    }

    public static void main(String[] args) {
        Graph g = new Graph(5);
        g.addEdge(0, 1, 9);
        g.addEdge(0, 2, 6);
        g.addEdge(0, 3, 5);
        g.addEdge(0, 4, 3);
        g.addEdge(2, 1, 2);
        g.addEdge(2, 3, 4);

        g.dijkstra(0);
    }
}

벨만-포드 알고리즘 (Bellman-Ford Algorithm)

벨만-포드 알고리즘은 음의 가중치가 포함된 그래프에서도 사용할 수 있는 최단 경로 탐색 알고리즘이다. 이 알고리즘은 모든 정점을 반복적으로 검토하고, 각 간선을 확인하여 최단 경로를 업데이트해. 다익스트라 알고리즘보다 느리지만, 음의 가중치 사이클이 있는지도 검출할 수 있는 장점이 있다.

작동 방식
시작 정점을 제외한 모든 정점의 거리를 무한대로 설정한다.
각 간선에 대해, 시작 정점으로부터의 거리를 계산하여 필요한 경우 업데이트해. 위의 과정을 정점 수 V만큼 반복한다.
V−1번 반복 후, V번째 반복에서 거리가 업데이트 되면 그래프에 음의 사이클이 있는 것으로 간주한다.

import java.util.Arrays;

class Edge {
    int src, dest, weight;
    Edge(int s, int d, int w) {
        src = s;
        dest = d;
        weight = w;
    }
}

public class BellmanFord {
    private int vertices;
    private Edge[] edges;
    private int edgeCount;

    public BellmanFord(int v, int e) {
        vertices = v;
        edges = new Edge[e];
        edgeCount = 0;
    }

    public void addEdge(int src, int dest, int weight) {
        edges[edgeCount++] = new Edge(src, dest, weight);
    }

    public void bellmanFord(int src) {
        int[] dist = new int[vertices];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[src] = 0;

        for (int i = 1; i < vertices; 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;
                }
            }
        }

        // Check for negative-weight cycles
        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;
            }
        }

        // Printing the results
        System.out.println("Vertex Distance from Source");
        for (int i = 0; i < vertices; i++) {
            System.out.println(i + "\t\t" + dist[i]);
        }
    }

    public static void main(String[] args) {
        BellmanFord graph = new BellmanFord(5, 8);
        graph.addEdge(0, 1, -1);
        graph.addEdge(0, 2, 4);
        graph.addEdge(1, 2, 3);
        graph.addEdge(1, 3, 2);
        graph.addEdge(1, 4, 2);
        graph.addEdge(3, 2, 5);
        graph.addEdge(3, 1, 1);
        graph.addEdge(4, 3, -3);

        graph.bellmanFord(0);
    }
}