[알고리즘] 다익스트라 + 플로이드 워샬 구현 (Swift)

합승 택시 요금 문제를 풀다가 다익스트라랑 플로이드 워샬에 대해 정리하고 가려고 합니다 . .

 

문제는 가중치 있는 그래프가 주어지고,

시작점[s]으로부터 특정 한 지점[i]을 거쳐 결국 다른 두 개의 도착지[a, b]에 도착하는 최단거리를 구하면 되는 문제입니다.

다익스트라

가장 먼저 다익스트라 풀이를 생각했습니다.

다익스트라는 최단거리를 갱신해나가는 알고리즘으로 일종의 dp 방식입니다.

코드로 구현하는 게 오늘 포스팅의 목적이기 때문에 알고리즘은 간단하게 설명할게요 . . !

 

1. 최단 거리 저장하는 배열 dist[]를 INF로 초기화

2. 시작점부터 인접한 노드들 돌면서 최단 거리 갱신

    - priorityQueue 사용하여 cost 가장 낮은 노드순으로 pop하기

    - dist[다음노드] > 현재 거리 + 다음노드 거리 라면 최단거리 update

    - dist[현재노드] < 현재거리면 건너뛰기 (이거 안했더니 시간초과)

3. 시작점을 s로 해서 다익스트라 실행 - distFirst[]

    시작점을 i in  1 ~ n으로 해서 다익스트라 실행 - dist[]

    s → i + i → a + i → b 의 최솟값 구하기

 

[코드]

func dijkstra(_ s: Int, _ dist: [Int]) -> [Int] {
    var dist = dist
    dist[s] = 0
    pq.insert(EdgeData(node: s, cost: 0))
    
    while !pq.isEmpty {
        let cur = pq.delete()
        let (curNode, curDist) = (cur.node, cur.cost)
        
        if dist[curNode] < curDist {
            continue
        }
        
        for (nxtNode, nxtCost) in graph[curNode]! {
            let nxtDist = curDist + nxtCost
            
            if nxtDist < dist[nxtNode] {
                dist[nxtNode] = nxtDist
                pq.insert(EdgeData(node: nxtNode, cost: nxtDist))
            }
        }
    }
    
    return dist
}

Heap이랑 EdgeData는 미리 구현해놓은 구조체입니다.

깃허브 링크 걸어둘게요 !

플로이드 와샬

다른 풀이들을 찾아보니까 플로이드 와샬로 대부분 풀었더라고요 . .

O(V^3) 시간 복잡도라서 당연히 배제했네요 . . 

문제에서 n의 제한사항이 200이기 때문에 플로이드 와샬을 쓸 수 있겠군요.

앞으로 제한사항 확인하고 n이 10^2면 플로이드 와샬을 생각하면 될 것 같아요.

 

플로이드 와샬 알고리즘의 핵심은 "모든 정점"에서 "모든 정점"으로의 최단경로를 구할 수 있다는 것인데요 .

역시 간단하게만 설명할게요.

 

1. 최단거리 저장하는 배열 dist 무한대로 초기화

2. dist[i][i] = 0 자기자신의 경우 0으로 초기화

3. 인접 행렬들에 간선의 정보 저장 (초기화)

    dist[i][j] = cost

    dist[j][i] = cost

4. 3중 포문 돌면서 최단거리 갱신

for k in 1...n {
    for i in 1...n {
        for j in 1...n {
            if dist[i][j] > dist[i][k] + dist[k][j] {
                dist[i][j] = dist[i][k] + dist[k][j]
            }
        }
    }
}

 

k : 거쳐가는 노드

i : 시작 노드

j : 도착 노드

 

dist[i][j] > dist[i][k] + dist[k][j] 의 의미는 i → j 로 가는 거리보다 i → k → j 로 가는 거리가 더 짧다는 의미 !

 

5. 문제 조건에 맞게 정답 구하기

ans = dist[s][a] + dist[s][b]

for i in 1...n {
    ans = min(ans, dist[s][i] + dist[i][a] + dist[i][b])
}

 

문제 하나 푸는데 . .

heap이랑 priorityQueue 구현부터 . . 다익스트라랑 플로이드 와샬까지 싹 공부하게 되었네요 . .

꼭 며칠 후에 다시 풀어보자 . ! 안그럼 까먹는다 !