최단 경로 (다익스트라, 플로이드 워셜 알고리즘)

본 글은 '이것이 취업을 위한 코딩 테스트다 with 파이썬' 책을 공부하며 기록합니다.
단, iOS를 공부하고 있기 때문에 swift 언어로 코드를 바꿔보고 있습니다.

최단 경로

가장 짧은 경로를 찾는 알고리즘. '길 찾기' 문제 라고도 불린다.

상황에 맞는 효율적 알고리즘이 정해져 있다!

예

• 한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우
• 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우

보통 그래프를 이용하여 표현되고, 각 지점은 노드로, 지점 간 연결된 도로는 간선으로 표현된다. 보통은 최단 거리를 출력하는 문제가 많다.

대표적 알고리즘

• 다익스트라 최단 경로 알고리즘
• 플로이드 워셜
• 벨만 포드 알고리즘

다익스트라 최단 경로 알고리즘과 플로이드 워셜 알고리즘이 가장 많이 나옴.

그리디 알고리즘과 다이나믹 프로그래밍 알고리즘의 한 유형으로 볼 수 있음.

다익스트라 최단 경로 알고리즘

한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우

특정한 노드에서 출발해서 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘.

'음의 간선'이 없을 경우에 동작.

매번 가장 비용이 적은 노드를 선택하기 때문에 그리디 알고리즘으로 분류된다.

[과정]

1. 출발 노드 설정
2. 최단 거리 테이블 초기화
3. 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드를 선택
4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신
5. 3-4 과정 반복

각 노드에 대한 현재까지의 최단 거리 정보를 1차원 리스트에 저장하며 리스트를 계속 갱신해 나간다.

 

다익스트라 알고리즘을 구현하는 2가지 방법

1. 구현하기 쉽지만 느린 코드

O(V^2)의 시간 복잡도 (V는 노드 개수)

노드의 개수가 5000개 이하라면 가능하지만 그 이상일 경우에는 해결하기 어려운 방법

각 단계마다 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드를 선택하기 위해 1차원 리스트의 모든 원소를 확인(순차 탐색)한다.

 /// 간단한 다익스트라 알고리즘 구현
 // n = 노드 개수, m = 간선 개수
 let n = inputs[0], m = inputs[1]

 let start = Int(readLine()!)!
 var graph = Array(repeating: [(Int, Int)](), count: n + 1)
 var visited = Array(repeating: false, count: n + 1)
 var distance = Array(repeating: Int.max, count: n + 1)

 for _ in 0..<m {
     let values = readLine()!.split(separator: " ").map { return Int($0)! }
     let a = values[0], b = values[1], c = values[2]

     // a-b 사이의 거리 c 저장
     graph[a].append((b, c))
 }

 // 방문하지 않은 노드 중 최단 거리의 노드 번호 반환
 func getSmallestNode() -> Int {
     var min = Int.max
     var index = 0
     for i in 1..<n + 1 {
         if distance[i] < min && !visited[i] {
             min = distance[i]
             index = i
         }
     }
     return index
 }

 func dijkstra(_ start: Int) {
     // 시작 노드에 대한 초기화
     distance[start] = 0
     visited[start] = true

     for j in graph[start] {
         distance[j.0] = j.1
     }

     // 시작 노드를 제외한 전체 노드에 대해 최단 거리 계산
     for _ in 0..<n-1 {
         let now = getSmallestNode()
         visited[now] = true
         for j in graph[now] {
             let cost = distance[now] + j.1
             if cost < distance[j.0] {
                 distance[j.0] = cost
             }
         }
     }
 }

2. 구현하기 까다롭지만 빠르게 동작하는 코드

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

힙 자료구조를 사용하여 최단 거리에 있는 노드를 찾을 때 선형 시간이 아닌 로그 시간이 걸린다. 최단 거리의 노드를 찾기 위한 함수를 작성할 필요없이 우선순위 큐에서 꺼내오기만 하면 된다.

 /// 개선된(시간) 다익스트라 알고리즘 구현
 let inputs = readLine()!.split(separator: " ").map { return Int($0)! }
 // n = 노드 개수, m = 간선 개수
 let n = inputs[0], m = inputs[1]

 let start = Int(readLine()!)!
 var graph = Array(repeating: [(Int, Int)](), count: n + 1)
 var distance = Array(repeating: Int.max, count: n + 1)

 for _ in 0..<m {
     let values = readLine()!.split(separator: " ").map { return Int($0)! }
     let a = values[0], b = values[1], c = values[2]

     // a-b 사이의 거리 c 저장
     graph[a].append((b, c))
 }

 func dijkstra(_ start: Int) {
     var heap = MinHeap(Data(distance: 0, dest: start))
     distance[start] = 0
     while !heap.isEmpty() {
         guard let nowData = heap.pop() else { return }

         if distance[nowData.dest] < nowData.distance {
             continue
         }
         for i in graph[nowData.dest] {
             let cost = nowData.distance + i.1
             if cost < distance[i.0] {
                 distance[i.0] = cost
                 heap.insert(Data(distance: cost, dest: i.0))
             }
         }
     }
 }

 dijkstra(start)

 for i in 1..<n+1 {
     if distance[i] == Int.max {
         print("INFINITY")
     } else {
         print(distance[i])
     }
 }

+) swift 에서 무한대의 값으로 초기화 할 때 Int.max를 활용할 수 있다.

힙 자료구조

우선순위 큐를 구현할 때 사용하는 자료구조. 우선순위가 가장 높은 데이터를 가장 먼저 삭제한다.

최소 힙에서는 값이 가장 낮은 데이터가 먼저 삭제되고, 최대 힙은 값이 가장 큰 데이터가 먼저 삭제 된다. 다익스트라 최단 경로 알고리즘에서 비용이 적은 노드를 먼저 방문하기 때문에 최소 힙 구조를 사용하는 우선순위 큐를 이용하는 것이 좋다.

혹은 최소 힙을 최대 힙으로 사용하기 위해 우선순위 값에 음수 기호를 붙였다가 사용할 때 제거하는 트릭을 사용할 수도 있다.

Heap

Swift) 힙(Heap) 구현 해보기

위 블로그 참고!

힙은 완전 이진 트리로 구현한다.

완전 이진 트리
왼쪽 자식부터 채워지며, 마지막 레벨을 제외한 모든 자식 노드가 채워진 트리

최대 힙 (Max Heap)에서는 부모 노드의 값이 자식 노드의 값보다 같거나 커야하고, 최소 힙 (Min Heap)에서는 부모 노드의 값이 자식 노드의 값보다 같거나 작아야 한다. 형제 노드들 간의 관계는 상관이 없음.

따라서 루트 노드는 항상 최대 값 혹은 최소 값으로 유지된다.

배열로 구현하는 힙 (최대 힙)

1. 데이터 삽입

트리 구조에 맞게 데이터를 삽입한다 (배열의 마지막에 삽입). 삽입된 데이터의 크기가 부모의 데이터 보다 작(거나 같)을 때까지 swap

mutating func insert(_ data: T) {
     // 힙에 데이터가 없을 때
   if heap.count < 1 {
         heap.append(data)
         heap.append(data)
         return
     }

     // 1. 우선 삽입
     heap.append(data)

     // 부모 노드보다 큰 지 비교하고 인덱스를 반환하는 함수)
   func isBig(_ index: Int) -> Bool {
         if index == 1 {
         return false
     }

         let parentIndex = index / 2
       return heap[index] > heap[parentIndex] ? true: false
   }

     // 2. 부모 노드보다 작을 때까지 swap
   var index = heap.count - 1 // 삽입한 데이터의 인덱스 (마지막)
   while isBig(index) {
         let parentIndex = index / 2
     heap.swapAt(index, parentIndex)
       index = parentIndex
     }
 }

 

2. 데이터 꺼내기

힙에서 데이터를 꺼내는 것은 루트 노드에 있는 최대 값을 꺼낸다는 의미와 같다. 데이터를 가장 위에서 꺼내고 나면 남은 데이터를 재정렬해 주는 작업이 필요하다. 따라서 가장 마지막 원소를 루트 노드로 옮긴 후 자식 노드와 비교하여 데이터가 더 커질 때 까지 자식 노드 중 더 큰 값과 swap해 준다.

mutating func pop() -> T? {
     // 없으면 nil
     if heap.count <= 1 {
     return nil
     }

     // 1. 루트 노드와 마지막 노드 swap
   let returnData = heap[1]
   heap.swapAt(1, heap.count - 1)
   heap.removeLast()

   // 자식 노드와 비교하여 swap 해야하는 인덱스 반환
   func findIndex(_ index: Int) -> Int? {
       let leftIndex = index * 2
     let rightIndex = index * 2 + 1

     // 자식 노드가 없는 경우
     if leftIndex >= heap.count {
         return nil
     }

     // 하나의 자식 노드(왼쪽)만 있는 경우
     if rightIndex >= heap.count {
         return heap[leftIndex] > heap[index] ? leftIndex : nil
     }

     // 자식 노드가 모두 있을 때
     if heap[index] > heap[leftIndex] && heap[index] > heap[rightIndex] {
         return nil
     } else {
         return heap[leftIndex] < heap[rightIndex] ? rightIndex : leftIndex
     }
     }

     var index = 1

     // swap할 노드가 없을 때까지 반복 
     while findIndex(index) != nil {
         guard let swappedIndex = findIndex(index) else { return nil }
     heap.swapAt(index, swappedIndex)
     index = swappedIndex
     }

     return returnData
 }

시간 복잡도

힙은 삽입과 삭제 시 모두 트리를 재정렬(?)하는 과정이 필요하기 때문에 O(logN) 시간이 소요된다.

플로이드 워셜 알고리즘

모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우

노드 개수가 N개일 때 N번의 단계를 수행하며, 각 단계마다 O(N^2)의 연산을 수행한다. 따라서 총 시간 복잡도는 O(N^3)의 복잡도를 가진다.

다익스트라 알고리즘과 다르게 2차원 리스트에 최단 거리 정보를 저장한다.

각 단계에서는 해당 노드를 거쳐 가는 경우를 고려한다. 예로 1번 노드에 대해 확인할 때 1번 노드를 거쳐 지나가는 (A → 1번 → B) 모든 경우를 고려한다. 따라서 현재 확인하고 있는 노드 제외 N-1개의 노드에서 2개를 골라(A, B) A → 1번 → B로 가는 비용을 확인하여 최단 거리를 갱신한다. $_{N-1}P_2$개의 쌍을 단계마다 확인하며, $O(N^2)$의 시간이 걸린다.

이를 점화식으로 나타내면

위와 같이 쓸 수 있다. (다이나믹 프로그래밍의 일종)

$D_{ab}$는 a에서 b로 가는 최단거리

다음과 같은 그래프는 오른쪽과 같은 2차원 배열로 초기화 한다.

/// 플로이드 워셜 알고리즘 구현
let INF = 987654321
let n = Int(readLine()!)!, m = Int(readLine()!)!

var graph = Array(repeating: Array(repeating: INF, count: n + 1), count: n + 1)

// 자기 자신으로 가는 거리 0으로 초기화
for i in 1..<n + 1 {
    for j in 1..<n + 1 {
        if i == j {
            graph[i][j] = 0
        }
    }
}

// 간선 정보 입력받아 초기화
for _ in 0..<m {
    let values = readLine()!.split(separator: " ").map { return Int($0)! }
    let a = values[0], b = values[1], c = values[2]

    graph[a][b] = c
}

// 플루이드 워셜 알고리즘 수행 (3중 for문)
for k in 1..<n + 1 {
    for a in 1..<n + 1 {
        for b in 1..<n + 1 {
            // 점화식 수행
            graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])
        }
    }
}

 

참고

https://book.naver.com/bookdb/book_detail.nhn?bid=16439154

Swift) 힙(Heap) 구현 해보기