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

본 내용은 '이것이 취업을 위한 코딩테스트다 with 파이썬' 책을 기반으로 포스팅 하였습니다.

최단경로 알고리즘

• 최단경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘이다.
• 각 지점은 그래프에서 노드로 표현된다.
• 지점 간 연결된 도로는 그래프에서 간선으로 표현된다.

 

다양한 문제 상황 

1. 한 지점에서 다른 한 지점까지의 최단 경로
2. 한 지점에서 다른 모든 지점까지의 최단 경로
3. 모든 지점에서 다른 모든 지점까지의 최단 경로

 

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

• 다익스트라 최단 경로 알고리즘은 그래프에서 여러 개의 노드가 있을 때 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다.
• 다익스트라 최단 경로 알고리즘은 음의 간선이 없을 때 정상적으로 동작한다.
• 음의 간선이란 0보다 작은 값을 가지는 간선을 의미한다.
• 다익스트라 최단 경로 알고리즘은 매번 가장 비용이 적은 노드를 선택해서 임의의 과정을 반복하기 때문에 그리디 알고리즘으로 분류된다.

 

특징

• 최단경로를 구하는 과정에서 각 노드에 대한 현재까지의 최단거리 정보를 항상 1차원 리스트에 저장하며 리스트를 계속 갱신한다.

 

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

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

 

구현하는 방법 2가지

1. 구현하기 쉽지만 느리게 동작하는 코드
2. 구현하기에 조금 더 까다롭지만 빠르게 동작하는 코드

 

간단한 다익스트라 알고리즘

1번 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 문제 ( 간단한 다익스트라 알고리즘)

• stap1 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드인 1번 노드 처리

• step2 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드인 4번 노드 처리

• step3 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드인 2번 노드 처리

• step4 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드인 5번 노드 처리

• step5 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드인 3번 노드 처리

• step6 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드인 6번 노드 처리

간한단 다익스트라 알고리즘  소스코드

// 노드의 개수와 간선의 개수 입력 받기
let input = readLine()!.components(separatedBy: " ").map({Int($0)!})

// 시작 노드 입력 받기
let start = Int(readLine()!)!

// 각 노드에 연결되어있는 다른 노드들의 정보를 담는 배열 초기화
var graph = Array(repeating: Array(repeating: [Int](), count: 0), count: input[0] + 1)

// 각 노드에 방문 체크를 위한 배열 초기화
var visited = Array(repeating: false, count: input[0] + 1)

// 최단거리를 저장할 배열을 9999999999(무한)으로 초기화
var dp = Array(repeating: 9999999999, count: input[0] + 1)

// 모든 노드에 연결되어있는 간선에 대한 정보 입력 받기
for _ in 1...input[1] {
    let node = readLine()!.components(separatedBy: " ").map({Int($0)!})
    graph[node[0]].append(contentsOf: [[node[1],node[2]]])
}

// 최단거리를 저장한 배열중에 거리비용이 가장 짧은 노드번호를 반환
func getSmallstNode() -> Int {
    var minValue = 9999999999
    var index = 0
    
    // input[0] = 노드 개수
    for i in 1...input[0] {
        // 현재 노드의 거리비용이 minValue보다 작고, 방문하지 않은 노드일때 
        if dp[i] < minValue && !visited[i] {
            minValue = dp[i]
            index = i
        }
    }
    return index
}

func dijkstra() {
    // 시작 노드 초기화
    dp[0] = 0
    dp[1] = 0
    visited[1] = true
    
    // 시작노드와 연결되어있는 노드 거리 초기화
    for i in graph[start] {
        // i[0] = 노드 번호
        // i[1] = 거리 비용
        dp[i[0]] = i[1] 
    }
    
    // 시작노드를 제외한 전체 노드수 만큼 반복
    for i in 2...input[0] {
        // 거리비용이 가장 짧은 노드번호 저장
        let now = getSmallstNode()
        // 방문처리
        visited[i] = true
        
        // 현재 노드와 연결된 다른 노드 확인
        for j in graph[now] {
        	// 현재노드의 거리비용 + 다른노드의 거리비용 
            let cost = dp[now] + j[1]
            
            // 현재 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧으면
            if cost < dp[j[0]] {
            	// 현재노드를 거쳐가는 노드에 cost 저장
                dp[j[0]] = cost
            }
        }
    }
}

dijkstra()

for i in 1...input[0] {
    print(dp[i])
}

간한단 다익스트라 알고리즘 성능 분석
1. 총 O(V)번에 걸쳐서 최단 거리가 가장 짧은 노드를 매번 선형 탐색해야한다. 따라서 전체 시간 복잡도는 O(V^2)
2. 일반적으로 전체 노드의 개수가 5000개 이하라면 위 코드로 문제 해결 가능 하지만 10000만개 이상일때는 어려움

 

개선된 다익스트라 알고리즘

• 개선된 다익스트라 알고리즘에서는 힙 자료구조를 사용한다.
• 힙 자료구조를 이용하게 되면 특정 노드까지의 최단 거리에 대한 정보를 힙에 담아서 처리하므로 출발 노드로부터 가장 거리가 짧은 노드를 더욱 빠르게 찾을 수 있다.

 

힙 

• 힙 자료구조는 우선순위 큐를 구현하기 위하여 사용하는 자료구조중 하나다.

 

우선순위 큐

• 우선순위가 가장 높은 데이터를 가장 먼저 삭제한다는 특징이 있다.
• 우선순위 큐를 구현할 때는 내부적으로 최소 힙 또는 최대 힙을 이용한다.
• 스택, 큐, 우선순위 큐 자료구조 비교 

자료 구조	추출되는 데이터
스택	가장 나중에 삽입된 데이터
큐	가장 먼저 삽입된 데이터
우선순위 큐	가장 우선순위가 높은 데이터

• 구현 방식에 따른 시간 복잡도

우선순위 큐 구현 방식	삽입 시간	삭제 시간
리스트	O(1)	O(N)
힙(Heap)	O(logN)	O(logN)

 

1번 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 문제 ( 개선된 다익스트라 알고리즘)

• step1 우선순위 큐에서 원소를 꺼냅니다. 1번 노드는 아직 방문하지 않았으므로 이를 처리합니다.

• step2 우선순위 큐에서 원소를 꺼냅니다. 4번 노드는 아직 방문하지 않았으므로 이를 처리합니다.

• step3 우선순위 큐에서 원소를 꺼냅니다. 2번 노드는 아직 방문하지 않았으므로 이를 처리합니다.

• step4 우선순위 큐에서 원소를 꺼냅니다. 5번 노드는 아직 방문하지 않았으므로 이를 처리합니다.

• step5 우선순위 큐에서 원소를 꺼냅니다. 3번 노드는 아직 방문하지 않았으므로 이를 처리합니다. 

• step6 우선순위 큐에서 원소를 꺼냅니다. 3번 노드는 이미 방문했으므로 무시합니다.

• step7 우선순위 큐에서 원소를 꺼냅니다. 6번 노드는 아직 방문하지 않았으므로 이를 처리합니다.

• step8 우선순위 큐에서 원소를 꺼냅니다. 3번 노드는 이미 방문했으므로 무시합니다.

 

개선된 다익스트라 알고리즘 소스코드

class Heap<T: Comparable> {
    var heapArray: [[T]]
    var root: T? {
        if isMaxHeap {
            maxHeapify()
        } else {
            minHeapify()
        }
        return heapArray[0].first
    }
    var count: Int {
        return heapArray.count
    }
    var isEmpty: Bool {
        return heapArray.isEmpty
    }
    var isMaxHeap: Bool

    init(_ n: [[T]], isMaxHeap: Bool) {
        heapArray = n
        self.isMaxHeap = isMaxHeap
    }
    func isLeftChildExist(_ parent: Int) -> Bool {
        if parent * 2 + 1 >= count {
            return false
        } else {
            return true
        }
    }
    func isRightChildExist(_ parent: Int) -> Bool {
        if parent * 2 + 2 >= count {
            return false
        } else {
            return true
        }
    }
    func parentIndex(_ child: Int) -> Int {
        return child / 2
    }
    func leftChildIndex(_ parent: Int) -> Int {
        return parent * 2 + 1
    }
    func rightChildIndex(_ parent: Int) -> Int {
        return parent * 2 + 2
    }
    func maxHeapify() {
        isMaxHeap = true
        var i = count / 2
        while i >= 0 {
            var bigChild: Int = 0
            if isLeftChildExist(i) && isRightChildExist(i) {

                if heapArray[leftChildIndex(i)].first! <= heapArray[rightChildIndex(i)].first! {
                    bigChild = rightChildIndex(i)
                } else {
                    bigChild = leftChildIndex(i)
                }
            } else if isLeftChildExist(i) && !isRightChildExist(i) {
                bigChild = leftChildIndex(i)
            } else if !isLeftChildExist(i) && !isRightChildExist(i) {
                i -= 1
                continue
            }

            if heapArray[bigChild].first! >= heapArray[i].first! {
                let temp = heapArray[bigChild]
                heapArray[bigChild] = heapArray[i]
                heapArray[i] = temp
            }
            i -= 1
        }
    }
    func minHeapify() {
        isMaxHeap = false
        var i = count / 2
        while i >= 0 {
            var smallChild: Int = 0
            if isLeftChildExist(i) && isRightChildExist(i) {
                if heapArray[leftChildIndex(i)].first! >= heapArray[rightChildIndex(i)].first! {
                    smallChild = rightChildIndex(i)
                } else {
                    smallChild = leftChildIndex(i)
                }
            } else if isLeftChildExist(i) && !isRightChildExist(i) {
                smallChild = leftChildIndex(i)
            } else if !isLeftChildExist(i) && !isRightChildExist(i) {
                i -= 1
                continue
            }

            if heapArray[smallChild].first! <= heapArray[i].first! {
                let temp = heapArray[smallChild]
                heapArray[smallChild] = heapArray[i]
                heapArray[i] = temp
            }
            i -= 1
        }
    }
    func popRoot() -> [T]?{
        if isMaxHeap {
            maxHeapify()
        } else {
            minHeapify()
        }
        if !heapArray.isEmpty {
            let temp = heapArray[heapArray.count - 1]
            heapArray[heapArray.count - 1] = heapArray[0]
            heapArray[0] = temp
        }
        let rootValue = heapArray.popLast()

        return rootValue
    }
    func push(_ n: [T]) {
        heapArray.append(n)
    }
}


// -----------------------------------------------------------------------------------
// 문제 풀이 코드 

// 노드의 개수와 간선의 개수 입력 받기
let input = readLine()!.components(separatedBy: " ").map({Int($0)!})

// 시작 노드 입력 받기
let start = Int(readLine()!)!

// 각 노드에 연결되어 있는 다른 노드들의 정보를 담는 배열 초기화
var graph = Array(repeating: Array(repeating: [Int](), count: 0), count: input[0] + 1)

// 최단거리를 저장할 배열을 9999999999(무한)으로 초기화
var dp = Array(repeating: 9999999999, count: input[0] + 1)


// 모든 노드에 연결되어있는 간선에 대한 정보 입력받기
for _ in 1...input[1] {
    let node = readLine()!.components(separatedBy: " ").map({Int($0)!})
    graph[node[0]].append(contentsOf: [[node[1],node[2]]])
}


func dijkstra() {

    // 큐 배열 초기화 (최소 힙)
    let heap = Heap.init([[Int]](), isMaxHeap: false)
    
    // 시작노드로 가기위한 최단 경로 0으로 초기화 후 큐에 삽입
    heap.push([0, start])
    // 시작노드 최소거리 배열 초기화 
    dp[0] = 0
    dp[start] = 0

    // 큐가 비어있지 않으면 반복 
    while !heap.heapArray.isEmpty {

        // 큐에 저장되어 있는 정보중 최단거리가 가장 짧은 노드에 대한 정보 꺼내기 [거리비용, 노드번호]
        let dist = heap.popRoot()!
        let now = dist[1]

        // 현재노드의 거리비용이 큐에서 꺼낸 정보의 거리비용보다 작다면 다음 반복 수행
        if dp[now] < dist[0] {
            continue
        }

        // 현재 노드와 연결된 다른 노드 확인
        for i in graph[now] {
            // 큐에서 꺼낸 정보의 거리비용 + 다른 노드의 거리 비용 
            let cost = dist[0] + i[1]

            // 현재 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧으면
            if cost < dp[i[0]] {
                // 현재노드를 거쳐가는 노드에 cost 저장
                dp[i[0]] = cost
                // 큐에 [거리비용, 현재노드를 거쳐가는 노드번호] 삽입
                heap.push([cost,i[0]])
            }
        }
    }
}

dijkstra()

// 결과 출력
for i in 1...input[0] {
    if dp[i] == 9999999999 {
        print("무한")
    } else {
        print(dp[i])
    }
}

간한단 다익스트라 알고리즘 성능 분석
1. 총 O(V)번에 걸쳐서 최단 거리가 가장 짧은 노드를 매번 선형 탐색해야한다. 따라서 전체 시간 복잡도는 O(V^2)
2. 일반적으로 전체 노드의 개수가 5000개 이하라면 위 코드로 문제 해결 가능 하지만 10000만개 이상일때는 어려움

개선된 다익스트라 알고리즘 성능 분석
1. 힙 자료구조를 이용하는 다익스트라 알고리즘의 시간 복잡도는 O(ElongV)이다.
2. 노드를 하나씩 꺼내 검사하는 반복분(While문)은 노드의 개수 V 이상의 횟수로 처리하지 않는다.
     -. 결과적으로 현재 우선순위 큐에서 꺼낸 노드와 연결된 다른 노드들을 확인하는 총 횟수는 최대 간선의 개수(E)만큼 연산이 수          행될 수 있다.
3. 직관적으로 전체 과정은 E개의 원소를 우선순위 큐에 넣었다가 모두 빼내는 연산과 유사하다.

 

참고자료 

https://www.youtube.com/watch?v=acqm9mM1P6o&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=7