다익스트라 알고리즘 Swift

알고리즘 문제를 풀면서, 최단경로를 구하는 문제에서 BFS 혹은 DFS를 이용해 문제를 푸려다, 늘 시간초과와 함께했다..

이번에는 특정 노드로 가는데 걸리는 최단경로를 구하기에 용이한 다익스트라 알고리즘을 배우려한다.

 

다익스트라 알고리즘

 다익스트라 알고리즘은 다이나믹 프로그래밍을 활용한 최단경로를 구하는 탐색 알고리즘이다.

이는 실생활에서 최단경로를 구하는데 용이한 알고리즘으로 어떠한 그래프든 방향과 상관이 없지만, 실생활에서 음수의 경로는 없듯이

가중치가 음수인 그래프는 사용할 수 없다.

다익스트라 알고리즘은 하나의 최단거리를 구할때, 이전의 최단거리를 이용하여 구한다는점이 다이나믹 프로그래밍의 특징이라 알 수 있다.

다익스트라는 하나의 노드로 부터 최단경로를 구하는 알고리즘 이지만, 플로이드-워셜 알고리즘은 모든 노드쌍들의 최단거리를 구한다.

다익스트라의 확장된 알고리즘으론 A* 알고리즘이 있다.

 

알고리즘 작동 과정

이 그래프에서 우리는 A지점에서 출발 한다고 하자.

A에서 출발해 인접한 노드들로 갈 것이다. (B, C)

현재 우리는 B,C의 최단거리를 알고 있다.(B = 5, C = 1)

그 다음 A에서 C로 간다면, C의 인접한 노드들의 최단거리를 갱신하게되며, A에서B로가는 최단거리는 A - C - B = 3 이 된다.

-> A에 있을땐 B와의 최단거리는 5로 알고있지만, C로 가보았다면 B의 최단거리는 3이 됨을 알 수 있다.

이렇게 인접한 노드들의 거리를 이용해, 현재 최단거리의정보를 계속 갱신해나가는 것이다.

 

1. 출발점을 지정한다.

2. 출발노드와 인접한 노드들의 최단거리를 갱신한다.

3. 인접한 노드들 중 거리가 짧은 노드를 선택한다.

4. 선택한노드와 인접한 노드의 거리로 최단거리 정보를 갱신한다.

5. 3-4 반복

 

 

A지점에서는 B와 C로 갈 수 있고, D, E는 갈 수 없다.

이를 표로 나타내면 다음 과 같다. 이 표는 현재 최단거리의 정보를 저장한 표다.

A	B	C	D	E
0	5	1	INF	INF

 

 

그 다음노드는 인접한 노드들중 가장 가까운 거리를 먼저 간다.

 

C에 도착했다면 현재 저장된 최단거리와 C와 인접한 노드들의 거리를 계산하여 갱신한다.

B: C까지의 최단거리 + (C-B) = 3

D: C까지의 최단거리 + (C-D) = 5 

A	B	C	D	E
0	3	1	5	INF

 

 

그 다음 방문하지 않은 노드중 가장 비용이 적은 노드를 고른다.

B를 방문했을때, 인접한노드들과 최단거리정보와 비교한다.

D: B까지의 최단거리 + (B-D): 4

E: B까지의 최단거리 + (B-E): 7

A	B	C	D	E
0	3	1	4	7

 

그다음 방문하지 않은 노드중 비용이 적은 노드를 방문한다.

D를 방문했을때, 인접한노드 E의 최단거리를 갱신한다.

E: D까지의 최단거리 + E = 4 + 2 = 6

A	B	C	D	E
0	3	1	4	6

 

마지막 남은 노드를 방문한다.

해당 노드를 방문해도 최단거리 배열은 같다.

A	B	C	D	E
0	3	1	4	6

 

 

다익스트라 알고리즘은 가중치가 가장 낮은 인접 노드를 우선으로 탐색하지만,

선형탐색으로 가중치와 관계없이 인접한 노드를 탐색하는 방법 도 있다.

하지만 선형탐색으로 탐색한다면 O(N^2)가 걸리고, Heap구조를 이용해 구현한다면 O(NlogN)만큼 걸리게된다.

선형탐색은 노드 수가 많을수록 치명적이다.

 

선형탐색 O(N^2)

import Foundation

// 그래프 2차원배열 graph[1][2] -> 노드1과 노드2의 가중치, 10000000은 임의의 큰 값 (연결되지않음)
var graph = [
    [0, 5, 1, 10000000, 10000000],
    [5, 0, 2, 1, 4],
    [1, 2, 0, 4, 10000000],
    [10000000, 1, 4, 0, 2],
    [10000000, 4, 10000000, 2, 0]
]
// 출발점 지정
var needVisit = [(cur: 0, cost: 0)]

// 현재 최단거리를 저장할 배열
// ex) minDistances[1]: 출발점에서 노드1까지의 최단거리
var minDistances = Array(repeating: 10000000, count: graph.count)
minDistances[0] = 0

// 탐색
while !needVisit.isEmpty {
    let node = needVisit.removeFirst()
    // 노드와 인접한 노드들을 탐색한다.
    for i in 0..<graph[node.cur].count {
        let dist = graph[node.cur][i]
        // 노드와 연결되어 있고, 현재 저장된 최단거리 + 해당노드와의 거리가 더 작은값이라면 갱신
        // 갱신된 노드와 최단거리와 함께 큐에 재삽입
        if dist != 10000000 && node.cost + dist < minDistances[i] {
            minDistances[i] = node.cost + dist
            needVisit.append((cur: i, cost: minDistances[i]))
        }
    }
}

 

결과:

// 결과
// A와의 인접노드: B,C
selectedNode: (cur: 0, cost: 0)
before: [0, 10000000, 10000000, 10000000, 10000000]
after: [0, 5, 1, 10000000, 10000000]
needVisit: [(cur: 1, cost: 5), (cur: 2, cost: 1)]

// B와의 인접노드: A,C,D,E
selectedNode: (cur: 1, cost: 5)
before: [0, 5, 1, 10000000, 10000000]
after: [0, 5, 1, 6, 9]
needVisit: [(cur: 2, cost: 1), (cur: 3, cost: 6), (cur: 4, cost: 9)]

// C와의 인접노드: A,B,D
// 여기서 B의 최단거리가 C를 통해 가는게 더 작은값임을 알고, 갱신하고 B를 재탐색하기위해 큐에 삽입)
// D도 갱신되어 큐에 삽입
selectedNode: (cur: 2, cost: 1)
before: [0, 5, 1, 6, 9]
after: [0, 3, 1, 5, 9]
needVisit: [(cur: 3, cost: 6), (cur: 4, cost: 9), (cur: 1, cost: 3), (cur: 3, cost: 5)]

// D와의 인접노드: B,C,E
// E의최단거리 갱신되어, E를 큐에 삽입
selectedNode: (cur: 3, cost: 6)
before: [0, 3, 1, 5, 9]
after: [0, 3, 1, 5, 8]
needVisit: [(cur: 4, cost: 9), (cur: 1, cost: 3), (cur: 3, cost: 5), (cur: 4, cost: 8)]

// E와의 인접노드: B,D
// 갱신되지않음.
selectedNode: (cur: 4, cost: 9)
before: [0, 3, 1, 5, 8]
after: [0, 3, 1, 5, 8]
needVisit: [(cur: 1, cost: 3), (cur: 3, cost: 5), (cur: 4, cost: 8)]

// 아래부턴 갱신된 최단거리를 통해 다시 노드를 선택하여 인접한 노드와의 최단거리를 갱신한다.
selectedNode: (cur: 1, cost: 3)
before: [0, 3, 1, 5, 8]
after: [0, 3, 1, 4, 7]
needVisit: [(cur: 3, cost: 5), (cur: 4, cost: 8), (cur: 3, cost: 4), (cur: 4, cost: 7)]

selectedNode: (cur: 3, cost: 5)
before: [0, 3, 1, 4, 7]
after: [0, 3, 1, 4, 7]
needVisit: [(cur: 4, cost: 8), (cur: 3, cost: 4), (cur: 4, cost: 7)]

selectedNode: (cur: 4, cost: 8)
before: [0, 3, 1, 4, 7]
after: [0, 3, 1, 4, 7]
needVisit: [(cur: 3, cost: 4), (cur: 4, cost: 7)]
// E 갱신, 갱신된 최단거리와 함께 큐에 재삽입
selectedNode: (cur: 3, cost: 4)
before: [0, 3, 1, 4, 7]
after: [0, 3, 1, 4, 6]
needVisit: [(cur: 4, cost: 7), (cur: 4, cost: 6)]

selectedNode: (cur: 4, cost: 7)
before: [0, 3, 1, 4, 6]
after: [0, 3, 1, 4, 6]
needVisit: [(cur: 4, cost: 6)]

selectedNode: (cur: 4, cost: 6)
before: [0, 3, 1, 4, 6]
after: [0, 3, 1, 4, 6]
needVisit: []

Reference:

https://m.blog.naver.com/ndb796/221234424646