[알고리즘] 다익스트라 알고리즘 (Dijkstra Algorithm)

 

다익스트라(Dijkstra) 알고리즘 의 개념

 

다익스트라 알고리즘은 음의 가중치가 없는 한 정점에서 각 모든 정점까지의 최단거리를 구하는 알고리즘입니다. 이 과정에서 모든 다른 정점까지 최단 경로로 방문하여 각 정점까지의 최단 경로를 모두 찾을 수 있습니다.

 

다익스트라 알고리즘은 BFS 알고리즘과 다이나믹 프로그래밍을 사용한 알고리즘입니다.

 

 

 

 

다익스트라 알고리즘 동작 방법

초기세팅

1.  거리를 업데이트 해줄 배열 Array : [Int] 

2. 방문 했는지 안했는지 체크해줄 배열 Array : [Bool]

3. 우선순위 큐 (Heap 구조) -> 일반 큐도 가능하지만 비용이 작은 것부터 탐색하는 과정을 거치면 시간복잡도에서 이득입니다.

 

 

동작과정

1.  시작할 정점에 방문 처리한후 거리를 0으로 잡아줍니다.

2. 큐에 시작할 정점을 넣어줍니다.

3. 큐 반복문을 시작합니다 ( queue.count > 0 )

4. 방문한적 없는 노드 + 시작할 노드 주변 연결된 곳에 거리를 업데이트 합니다(초기값은 무한대 이기 때문에 무조건 업데이트 됩니다)

5. 거리를 업데이트 할때        방문할 곳의 거리값은 > 새로운 곳까지 거리 + 큐에서 뽑은 정점 거리 일때만 업데이트 합니다.

6. 우선순위 큐에 업데이트한 정점들을 넣어줍니다.

 

최종적으로 Array 에 최소 경로가 담긴 list가 됩니다.

 

 

 

다익스트라 과정 설명

 

https://cobi-98.tistory.com/46

 

목표는 A 노드에서 F노드로의 최단 경로를 구하는 문제입니다.

 

S -> 방문한 노드들의 집합

d[N] ->   A에서 N까지의 계산된 최단 거리

Q -> 방문하지 않은 정점들의 집합

 

시작 노드를 A로 잡아 방문을 시작합니다.

 

 

https://cobi-98.tistory.com/46

A에서 방문할 수 있는 B,C,D 의 값을 업데이트 해줍니다(초기값은 무한대라 바로 업데이트 가능)

 

 

 

https://cobi-98.tistory.com/46

B에서 방문 가능한 F 거리 없데이트 C 의 거리를 업데이트 하려고 보니 2 + 7 (A를 거쳐 B에서 C )은 5 (A에서 C) 보다 값이 큼으로 업데이트 하지 않습니다 최소 거리의 값이 중요하기때문입니다.

 

 

 

https://cobi-98.tistory.com/46

 

 

위의 과정과 마찬가지로 F 에서 방문가능한  C , E 의 값을 F 를 통해 거리를 더해줬을경우 작을때 업데이트 해줍니다

 

 

 

 

https://cobi-98.tistory.com/46

위의 과정과 동일합니다

 

 

 

 

https://cobi-98.tistory.com/46

 

 

 

https://cobi-98.tistory.com/46

 

모든 과정을 마쳤을때 d의 배열안에는 각노드의 최소 거리를 가진 배열을 확인하실수 있습니다. 

 

목적지가 F 임으로 A->D->C->E->F 가 최단 경로로 8 입니다

ex ) d[B] = 2 는 A에서 B 까지의 최소경로는 2

 

 

 

아래코드는 다익스트라를 이용한 Swift 백준 문제 코드입니다. 참고하시면서 코드를 따라가 보면 좋습니다.

import Foundation

// 백준 1753번 https://www.acmicpc.net/problem/1753
// 최소 힙 구현
struct Heap <T: Comparable> {
    var heap = [T]()

    private func getParent(_ index: Int) -> T {
        heap[index / 2]
    }

    private func getLeftChild(_ index: Int) -> T {
        heap[index * 2]
    }

    private func getRightChild(_ index: Int) -> T {
        heap[index * 2 + 1]
    }

    func isEmpty() -> Bool {
        heap.count <= 1
    }

    mutating func push(_ data: T) {
        if isEmpty() { heap.append(data) }
        var index = heap.count
        heap.append(data)

        while index > 1 {
            let parent = getParent(index)
            guard parent > data else { break }
            heap[index] = parent
            index /= 2
        }
        heap[index] = data
    }

    mutating func pop() -> T? {
        guard !isEmpty() else { return nil }
        let item = heap[1]
        let data = heap.removeLast()
        let size = heap.count - 1

        guard !isEmpty() else { return item }
        var (parent, child) = (1, 2)
        while child <= size {
            if child < size && getLeftChild(parent) > getRightChild(parent) {
                child += 1
            }
            guard data > heap[child] else { break }
            heap[parent] = heap[child]
            parent = child
            child *= 2
        }
        heap[parent] = data
        return item
    }
}

struct Node: Comparable {

    static func < (lhs: Node, rhs: Node) -> Bool {
        lhs.cost < rhs.cost
    }

    init(_ node: Int, _ cost: Int) {
        self.node = node
        self.cost = cost
    }
    
    let node: Int
    let cost: Int
    
    
}

let input = readLine()!.split(separator: " ").map { Int(String($0))! }
let (V,E) = (input[0], input[1])
let start = Int(readLine()!)!
var graph : [Int : [Node]] = [:]
var costList : [Int] = Array(repeating: Int.max, count: V+1)

for idx in 1...V {
    graph[idx] = []
}

for _ in 0..<E {
    let split = readLine()!.split(separator: " ").map { Int(String($0))! }
    let (start, end, value) = (split[0], split[1], split[2])
    graph[start]!.append(Node(end, value))
}

var queue = Heap<Node>()
var visited : [Bool] = Array(repeating: false, count: V+1)
costList[start] = 0
queue.push(Node(start, 0))


print(graph)

while let currentNode = queue.pop() {
    let (node, cost) = (currentNode.node, currentNode.cost)
    guard !visited[node] else {
        continue
    }
    visited[node] = true
    if let edge = graph[node] {
        for next in edge {
            let (nextNode, nextCost) = (next.node , next.cost)
            guard !visited[nextNode] else {
                continue
            }
            let newCost = cost + nextCost
            if newCost < costList[nextNode] {
                costList[nextNode] = newCost
                queue.push(Node(nextNode, newCost))
            }
        }
    }
}

for i in 1...V {
    if costList[i] == Int.max {
        print("INF")
    }else{
        print(costList[i])
    }

}

 

 

 

 

 

왜 사용해야할까 or 나만의 고민

첫지점과 목표지점의 최소의 거리(경로 추적에 좋음)를 구할때 사용합니다.

우선순위 대기열을 사용하여 모든 경로를 확인하는 무차별 접근 방식보다 효율적입니다.

하지만 음수의 가치를 가지면은 알고리즘이 정상적으로 돌아가지 않습니다.