[알고리즘] 최단 경로

최단 경로 알고리즘

---

음의 가중치가 없는 그래프에서 한 노드에서 다른 모든 노드까지의 최단 거리를 구하는 알고리즘이다.

방향 그래프, 무방향 그래프 모두 상관 없으나, 가중치가 음수인 edge가 하나라도 있으면 이 알고리즘은 사용할 수 없다.

 

 

 

최단 경로 문제의 유형

---

최단 경로의 문제 유형은 다음과 같다.

1. Single-source (one-to-all)
   하나의 출발 노드 s로부터 다른 모든 노드까지의 최단 경로를 찾아라
   예) 다익스트라 알고리즘
2. Single-pair (one-to-one)
   주어진 하나의 출발 노드 s로부터 하나의 목적지 노드 t까지의 최단 경로를 찾아라
   최악의 경우 시간복잡도에서 Single-source 문제보다 나은 알고리즘이 없기 때문에 해당 유형 또한 다익스트라 알고리즘이 사용된다.
3. All-pairs (all-to-all)
   모든 노드 쌍에 대해서 최단 경로를 찾아라
   예) 플로이드 와샬 알고리즘

 

 

 

최단 경로의 기본 특성

---

최단 경로의 기본적인 특성은 다음과 같다.

1. 최단 경로의 어떤 부분 경로도 역시 최단 경로이다.
2. 최단 경로는 사이클을 포함하지 않는다. (음수 사이클이 없다는 가정 하에서)

 

 

 

Single-source 최단 경로 문제

---

Single-source 최단 경로 문제에 대해 살펴보자.

• 입력: 음수 사이클이 없는 가중치 방향 그래프 G=(V, E)와 출발 노드 s $\in$ V
• 목적: 각 노드 v에 대해서 다음을 계산한다.
      1. d[v]
           처음에는 d[s] = 0, d[v] = $\infty$로 시작한다.
           알고리즘이 진행됨에 따라 d[v] 값은 감소해가고, 최종적으로 d[v]= 최단경로(s, v)가 된다.
      2.  s에서 v까지의 최단 경로상에서 v의 직전 노드(predecessor)
• 기본 연산: Relaxation (최단 경로 알고리즘의 핵심 연산이 릴렉스 연산이다.)

 

 

 

코드

---

Java 언어를 이용해 다익스트라 알고리즘을 살펴보자.

시작 정점에서 다른 모든 정점들로의 최단 거리를 distance[] 배열에 저장한다. (one-to-all)

class Main {
    public static void dijkstra(int start) {
        boolean[] visited = new boolean[100];
        PriorityQueue<Node> pq = new PriorityQueue<>();
        
        distance[start] = 0; // 시작점에서 시작점까지의 거리는 당연히 0이다.
        pq.add(new Node(start, 0)); // Node 클래스의 첫 번째 파라미터는 목적지 지점, 두 번째는 거리(가중치)다.
        
        while (!pq.isEmpty()) {
            Node currentNode = pq.poll();
            
            if (visited[currentNode.end]) continue;
            visited[currentNode.end] = true;
            
            // list에는 각 정점들의 경로가 저장되어 있다.
            // 예) list.get(1)은 1번 정점이 갈 수 있는 목적지 경로와 그 가중치가 저장되어 있다.
            for (Node node : list.get(currentNode.end)) {
                if (distance[node.end] > distance[currentNode.end] + node.weight) {
                    distance[node.end] = distance[currentNode.end] + node.weight;
                    pq.add(new Node(node.end, dist[node.end]);
                }
            }
        }
    }
}

 

 

 

참고자료

---

[1] https://namu.wiki/다익스트라 알고리즘