알고리즘

[SWIFT 알고리즘] 다익스트라 알고리즘(Lazy version)

옹홍 2021. 6. 10. 20:44

다익스트라 알고리즘은 Greedy 해결법과 DP 구현을 통해 Start point에서 terminate point 까지의 최단거리를 구하는 방법이다. 다익스트라 알고리즘은 negative edge가 없다면, 최단거리를 찾을 수 있다. 또한 다익스트라는 DAG일때 사용을 하지 않는다. DAG일 경우는 보통 위상정렬 알고리즘을 사용해서 최단거리를 구하는 것이 일반적이다. 

그래서 최단거리 알고리즘을 살펴보자면

  • BFS - 거리가 일정할때
  • 다익스트라 - 음수의 weight이 없을때
  • 위상정렬 - DAG일때, Directed acycling Graph(directed cycle이 없을때)
  • 벨만 포드 - negative cycle이 없을때
  • 플로이드 -  모든정점에서 모든 정점까지의 최단거리를 구할때

다익스트라 알고리즘의 첫번재 단계 : dist[] 초기화 시켜주기

dist[start] = 0으로 두고 나머지는 dist는 다 INF(무한대) 로 만들어준다. 여기서 dist 배열은 s에서 각 정점까지의 최단거리를 알려주는 배열이다. 현재 S = 0에서 갈수 있는 정점은 5, 8, 4 뿐이다. 

 

2번째 단계 : dist[]에서 가장 작은 정점으로부터 인접 정점까지의 weight을 파악하기

현재 dist = [0, INF, INF, INF, INF, INF, INF, INF] 이다. 이 상태에서 가장 작은 점 0의 인접 정점까지의 weight(distance)를 확인한다. 그렇다면, 0-1 : 5, 0-7 : 8, 0-9 : 5 이다. 그렇다면 이 3개의 weight은 모두 INF 보다 작다. 그렇다면 Relaxation이 시작된다. Relaxation은 아래에서 더 설명을 하겠다. 그렇다면 dist[0, 5, INF, INF, 9, INF, INF, 8] 이 된다. 여기서 우리는 가장 cost가 적은 1번 정점으로 가서 이 행위를 또한다.

1로 갔을 때, 0 -1 - 7 의 경로가 있다는 것을 확인했다. 이 경로의 weight은 0-1 : 5,  1-7: 4 이기에 총 9이다. 하지만 0-7은 8이기에 갱신이 되지 않느다. 결국 dist[1] + matrix[1][7] < dist[7]이 성립안해서 갱신이 되지 않는것이다. (아래 더 설명이 있다.)

 

다익스트라 알고리즘의 핵심은 Relaxation을 통해, dist[]라는 최단거리 리스트를 갱신시키는 것이다.

Relaxation은 짧은 길찾기이다. 더 짧은 길이 나오면 환승을 한다고 생각을 하면된다. 

 

가장 cost가 짧은 정점을 찾고(Greedy), 그 정점을 current라고 한다. current 값을 구할때, visited가 되지 않은 정점을 찾고, 이 중 가장 작은 값을 찾는다.  dist[current] + matrix[current][j] < dist[j] 라면 dist[j] = dist[current]+matrix[current][j]가 된다. 더 구체적인 예를 들자면, 다음 최소 cost 정점을 골랐을때, 그 정점이 4라고 하자. 그렇다면,포문을 돌면서 인접행렬을 도는것이다. for loop를 돌면서 if dist[4] + matrix[4][6] < dist[6]를 해본다. dist[6] 즉, 4를 고르기 전에 6까지 가는 최단거리와 4까지 가는 최단거리와, 4에서 6까지 가는 최단거리를 더한것을 비교하는 것이다. 그리고 더 작은 값으로 dist[6]을 갱신한다. 이것이 곧 Relaxation이다. 결국 다익스트라는 start 포인트를 시작으로, 먼저 dist[i]를 matrix[start][i]로 다 갱신하고, 그다음에, 그 중에 가장 작은 값을 찾고, 가장 작은 정점의 인접 정점까지의 거리를 조사해서, 더 작을 값을 dist[i]에 갱신한다고 생각하면 된다.

 

다익스트라 알고리즘은 풀때, 집합 형식으로 접근하는 방법도 존재한다.

  • Initialize dist[s] = 0, and dist[v] = 무한대 for all other vertices
  • Initialize X = {s};  // vertices processed so far(vertex는 여기까지 진행되었다는 뜻)
  • while(X != V)
    • Among all edges (v→w) with v ∈ X, w ∉ X, pick the one that minimizes
      “dist[v] + e.weight()”.
  • Add w to X, and update distance of all edges pointing from w
    o for each edge e = (w→z), dist[z] ≤ dist[w] + e.weight();

X라는 집합에 start vertex를 넣어주고 시작한다. v -> w로 가는 모든 edges 중에 v는 X에 포함되고, w는 X에 포함되지 않는다면, dist[v]+ e.weight 과 dist[w] 중 작은 것을 찾는다. 그리고 이제는 X 집합에 w를 포함시킨다. 이제는 w -> z 를 진행한다. 이때 w는 X집합에 포함되어있고, z는 그렇지않다. 

증명(다익스트라가 greedy 알고리즘이 되는이유)

v->w로 가는 edge에서 Relaxation을 지났다면, dist는 1번만 업데이트 된다. 그 이유는 dist[w]는 늘어나지 않고, dist[v]는 변하지 않기 때문이다. 왜냐면 dist[v]는 우리가 dist[]에서 가장 작은 값을 찾은 것이다. 그리고 dist[w] 역시 우리는 최소값으로 계속 갱신하고 있기 때문에, dist[w] 역시 늘어나지 않는다. 그래서 우리는 Greedy 해결법으로 가장 작은 값을 고른다음에, v ->w로 가는 길을 찾아서 더해줄 때, dist[w]와 비교를 할 수 있다. 

 

좀더 풀어서 이야기하자면, 현재 dist에서 가장 짧은 정점을 고르는 것은 그 정점은 더이상 갱신이 되지 않기 때문이다. 시작 지점 starting point에서 특정 정점까지 가장 짧은 distance를 골랐을때, 이 정점까지의 거리가 다시 갱신되려면, 결국 돌아가는길을 선택하는 것 뿐이다. 하지만 dist[]에서 가장 최소값을 골랐다는 이야기는 다른 정점으로 가는 길은 이미 그 최소값보다는 크다는 이야기일테고, 결국 어떠한 일이 있어도 돌아가는 길보다 바로 가는길이 가장 짧다는 것을 확인할 수 있다. 

 

다익스트라 알고리즘은 집합형식으로 진행되는 방향으로 생각한다고 했을때, starting point가 0이라고 하고, 그때 가장 짧은 거리가 정점 1로 가는 상황이라고 할 때, 정점 1를 집합에 넣는다. 그렇다면 어떠한 일이 있어도 0-1까지 가는 거리는 지금 선택한 dist가 가장 짧은거리가 된다. 이후에 0-7(바로) 가는 거리 vs 0-1-7(걸쳐서) 가는 거리를 비교했을때 마찬가지로 0-7이 더 작다면, dist를 갱신하지 않고, 이제 0에서 7까지 가는 최단거리는 정해진 것이라고 말할 수 있다. 왜냐면 지금 0,1 set에서 가장 짧은 거리가 8이라고 했을때, 다른 곳을 돌아가더라도 절대로 8보다 작은 값이 나올 수 없다.

다익스트라 알고리즘의 시간복잡도

배열로 진행할 경우

lazy version의 다익스트라 알고리즘의 시작복잡도는 O(V^2)이다. 가장 작은 정점을 고르는데 O(V)이고 그 정점을 기준으로 시작하는 모든 weight값을 적어둔 인접행렬을 전부다 돌아야하기 때문에, 이것도 O(V)가 된다. 이러한 진행방식을 모든 정점을 해야하기 때문에 결국은 O(V^2)가 된다.

 

이진힙(우선순위큐)으로 진행할 경우

다익스트라 알고리즘은 V번의 insert, V번의 delete-min, E번의 update-key가 진행된다. 여기서 E번의 update-key는 이진힙에서 각 v에 대한 cost를 update할때, v의 인접정점을 잇는 e들의 weight을 확인해야하기때문에, 결국은 모든 e를 한번 순회하는 결과를 띈다. 그리고 cost가 업데이트 되었을때, heapify가 진행되므로, E번 logV를 진행한다고 보면 된다. -> O(ElogV)

다익스트라 알고리즘에서 backtracking

다익스트라 알고리즘에서 백트래킹을 하고 싶다면, 우리는 다익스트라 알고리즘 표가 갱신될때, 즉, dist[next] =  dist[current] + matrix[current][next] 될 때, from[]을 하나 더 만들면된다. 즉, 우리는 from[next] = current를 넣어준다면, 결국 next에 오기 위해서는 current를 거쳐왔구나를 알 수 있다.

코드

let number = 6
let INF = 10000000

var g : [[Int]] = [[0,2,5,1,INF,INF],[2,0,3,2,INF,INF],[5,3,0,3,1,5], [1,2,3,0,1,INF],[INF,INF,1,1,0,2],[INF, INF, 5,INF,2,0]]
var visited = [Bool](repeating: false, count: 6)
var distance = [Int](repeating: 0, count: 6)
var from = [Int](repeating: 0, count: 6)

// return the mininum vartex
func getSmallIndex() -> Int {
    var min = INF
    var index = 0
    for i in 0..<number {
        if(distance[i] < min && !visited[i]){
            min = distance[i]
            index = i
        }
    }
    return index
}

func dijkstra(start: Int){
    for i in 0..<number {
        distance[i] = g[start][i]
    }
    visited[start] = true
    for i in 0..<number - 2 {
        var current = getSmallIndex()
        visited[current] = true
        for j in 0..<6 {
            if(!visited[j]){
                if(distance[current]+g[current][j] < distance[j]){
                    distance[j] = distance[current] + g[current][j]
                    from[j] = current
                }
            }
        }
    }
}

var start = 0
dijkstra(start: start)
print(distance)
print(from)