최단 경로 알고리즘

최단 경로 알고리즘은 두 노드 사이의 최단 경로를 찾는 알고리즘입니다. 그래프 이론에서 자주 사용됩니다.

가장 기본적인 최단 경로 알고리즘은 다익스트라 알고리즘입니다. 다익스트라 알고리즘은 음의 가중치를 가지지 않는 그래프에서 사용할 수 있으며, 시작 노드로부터 모든 다른 노드까지의 최단 경로를 찾을 수 있습니다. 이 알고리즘은 매우 효율적인 알고리즘으로 알려져 있으며, 우선순위 큐를 사용하여 구현할 수 있습니다.

그러나 음의 가중치를 가진 그래프에서는 벨만-포드 알고리즘이 사용됩니다. 이 알고리즘은 다익스트라 알고리즘과 달리 음의 가중치를 가진 그래프에서도 사용할 수 있습니다. 그러나 다익스트라 알고리즘보다 더 느린 실행 속도를 가지며, 음수 가중치 사이클이 있는 경우에는 최단 경로를 찾을 수 없습니다.

 

1. 다익스트라 알고리즘

 

가장 그래프 상의 두 노드를 연결하는 가장 짧은 경로를 찾는 방법으로 지도 경로 탐색, 네트워크 구축에 드는 비용을 최소하는 데에 사용할 수 있다.

 

- 출발점에서 목표점까지의 최단 경로를 구하는 알고리즘

- 한 노드에서 다른 모든 노드로의 최단 경로를 할 수 있음

- 간선에 음의 가중치가 없어야함 -> 벨만 포드 or 플로이드 워셜 가능

- 그리디 + DP 형태

- 시간 복잡도 : O(ElogV) V : 노드 수, E: 간선의 수

다익스트라 Flow, A부터 특정 Node까지 거리 계산

1)

node	A	B	C	D	E	F	G
distance	0	INF	INF	INF	INF	INF	INF

2) 최소 경로인 B를 선택해서 다음 Flow 진행

node	A(visited)	B	C	D	E	F	G
distance	0	2	6	INF	5	INF	INF

3)

node	A(visited)	B(visited)	C	D	E	F	G
distance	0	2	6 -> 4	INF -> 3	5	INF -> 9	INF

C : 2 + 2 와 기존 6의 최소값 비교해 : 4로 변경

D: INF -> 2 + 1 : 3

F : INF -> 2 + 7 : 9

4)

node	A(visited)	B(visited)	C	D(visited)	E	F	G
distance	0	2	4	3	5	9	INF - >6

5)

node	A(visited)	B(visited)	C(visited)	D(visited)	E	F	G
distance	0	2	4	I3	5	9	6

6)

node	A(visited)	B(visited)	C(visited)	D(visited)	E(visited)	F	G
distance	0	2	4	I3	5	9	6

7)

node	A(visited)	B(visited)	C(visited)	D(visited)	E(visited)	F(visited)	G(visited)
distance	0	2	4	I3	5	9->8	6

 

        for (int i = 0; i < data.length; i++) {
            graph.get(data[i][0]).add(new Node(data[i][1], data[i][2]));
        }

        int[] dist = new int[v + 1];

        for (int i = 1; i < v + 1; i++) {
            dist[i] = Integer.MAX_VALUE;
        }
        dist[start] = 0;

        boolean[] visited = new boolean[v + 1];

        for (int i = 0; i < v; i++) {
            int minDist = Integer.MAX_VALUE;
            int curIdx = 0;
            for (int j = 1; j < v + 1; j++) {
                if (!visited[j] && dist[j] < minDist) { // 최소 노드 정보로 시작
                    minDist = dist[j];
                    curIdx = j;
                }
            }

            visited[curIdx] = true;

            for (int j = 0; j < graph.get(curIdx).size(); j++) {
                Node adjNode = graph.get(curIdx).get(j);
                if (dist[adjNode.to] > dist[curIdx] + adjNode.weight) {
                    dist[adjNode.to] = dist[curIdx] + adjNode.weight;
                }
            }
        }

flow마다 최소 간선을 구하기 위해서 !visited && dist[j] < minDist를 비교해 구해서 index를 확인 후 다음 Flow로 넘어갔다. 최소 간선을 좀 더 편하게 구하기 위해서 우선순위 큐를 통해 구현이 가능하다.

        PriorityQueue<Node> pq = new PriorityQueue<>((x, y) -> x.weight - y.weight); //weight 기준으로 오름차순으로 정렬

        pq.offer(new Node(start, 0));

        while(!pq.isEmpty()){
            Node curNode = pq.poll();

            if (dist[curNode.to] < curNode.weight) {
                continue;
            }

            for (int i = 0; i < graph.get(curNode.to).size(); i++) {
                Node adjNode = graph.get(curNode.to).get(i);

                if (dist[adjNode.to] > curNode.weight + adjNode.weight) {
                    dist[adjNode.to] = curNode.weight + adjNode.weight;
                    pq.offer(new Node(adjNode.to, dist[adjNode.to]));

                }
            }
        }

 

2. 벨만-포드(Bellman-Ford)

 

- 음수 간선이 포함되어 있어도 최단 경로 구할 수 있음( 음수 사이클이 있으면 정상 동작 X)

- 매번 모든 간선을 확인하기 때문에 다익스트라에 비해 느림

- 알고리즘 복잡도 O(VE) 

 

 

벨만 포드 최종 결과

node	1	2	3	4	5	6	7
distance	0	8	3	7	5	10	3

 

모든 간선에 대해서 정점 수만큼 반복하면서 업데이트

 

   public static void bellmanFord(int v, int e, int[][] data, int start) {
        Edge[] edge = new Edge[e];

        for (int i = 0; i < e; i++) {
            edge[i] = new Edge(data[i][0], data[i][1], data[i][2]);
        }
        int[] dist = new int[v + 1];

        for (int i = 1; i < v + 1; i++) {
            dist[i] = Integer.MAX_VALUE;
        }

        dist[start] = 0;
        boolean isMinusCycle = false;

        for (int i = 0; i < v + 1; i++) {
            for (int j = 0; j < e; j++) {
                Edge cur = edge[j];

                if (dist[cur.from] == Integer.MAX_VALUE) {
                    continue;
                }
                if (dist[cur.to] > dist[cur.from] + cur.weight) {
                    dist[cur.to] = dist[cur.from] + cur.weight;

                    if (i == v) {
                        isMinusCycle = true;
                    }
                }
            }
        }
   }

3. 플로이드-워셜(Floyd-Warshall)

 

플로이드-워셜(Floyd-Warshall) 알고리즘은 모든 쌍 최단 경로 알고리즘 중 하나로, 음의 가중치를 가지는 그래프에서도 사용할 수 있습니다. 이 알고리즘은 다익스트라(Dijkstra) 알고리즘과 유사하지만, 다익스트라 알고리즘이 시작 노드로부터 각 노드까지의 최단 경로를 구하는 알고리즘이라면, 플로이드-워셜 알고리즘은 그래프 내의 모든 노드 쌍에 대한 최단 경로를 구하는 알고리즘입니다.

알고리즘의 기본 아이디어는 동적 계획법(Dynamic Programming)을 사용하는 것입니다. 시작 노드에서 노드 i까지의 최단 경로는 i를 거치지 않고 바로 갈 수 있는 경우와, i를 거쳐서 갈 수 있는 경우 중 작은 값을 선택합니다. 이를 모든 노드에 대해 반복하면 모든 쌍 최단 경로를 구할 수 있습니다.

플로이드-워셜 알고리즘의 시간 복잡도는 O(n^3)입니다. 따라서 그래프의 크기가 작을 때에는 다익스트라 알고리즘보다 느릴 수 있지만, 그래프의 크기가 커질수록 다익스트라 알고리즘이 각 노드까지의 최단 경로를 구하는 데에 매우 비효율적이므로, 플로이드-워셜 알고리즘이 더욱 유용해집니다.

 

import java.util.Arrays;

public class FloydWarshallAlgorithm {
    public static int[][] floydWarshall(int[][] graph) {
        int n = graph.length;
        int[][] dist = new int[n][n];
        
        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] != Integer.MAX_VALUE && 
                        dist[k][j] != Integer.MAX_VALUE &&
                        dist[i][k] + dist[k][j] < dist[i][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }
        }
        
        return dist;
    }
    
    public static void main(String[] args) {
        int[][] graph = {
            {0, 5, Integer.MAX_VALUE, 10},
            {Integer.MAX_VALUE, 0, 3, Integer.MAX_VALUE},
            {Integer.MAX_VALUE, Integer.MAX_VALUE, 0, 1},
            {Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, 0}
        };
        int[][] dist = floydWarshall(graph);
        for (int i = 0; i < dist.length; i++) {
            System.out.println(Arrays.toString(dist[i]));
        }
    }
}

플로이드-워셜(Floyd-Warshall) 알고리즘은 자기 자신으로 가는 경로가 음수가 되는 경우 경로 내에 음수 사이클이 있다고 판별할 수 있다.