Dijkstra Algorithm

[Taehyeon-Kim]

다익스트라

• 정점을 하나 선택하고 나머지 정점들로의 최단 거리를 모두 구함
• cost가 음수일때는 사용 불가(벨만 포드 알고리즘 사용 바람)
• 정점이 v개, 간선이 e개일때 O(ElgV) 시간 복잡도

기억해야할부분

• dist 배열 만들기 및 초기화(INF로 초기화)
• 최초 시작점 파악 후 초기화하기(시작점 0으로 초기화)
• 최단 거리 갱신하는 부분은 Heap, PriorityQueue로 구현 -> 그래야 시간적인 면에서 이득

다익스트라 구현 소스 코드

let INF = Int.max

var q = Heap<Int>()
var distance = [Int](repeating: INF, count: graph.count)

distance[0] = 0
q.push(0)

while let cur = q.pop() {
    for dest in 0..<graph[cur].count {
        // 갈수없거나 자기자신이면 스킵
        if graph[cur][dest] == INF || graph[cur][dest] == 0 { continue }
        
        let curViaDest = distance[cur] + graph[cur][dest]
        if curViaDest < distance[dest] {
            distance[dest] = curViaDest
            q.push(dest)
        }
    }
}

• 문자열 처리 까다로운 것보다 힘든 것은 Heap을 쌩구현해야한다는 것이다. STL 만들어줘;;;; (근데 이제 코드 다 외워서 없어도 됨)
• 다익스트라 이해 및 구현 과정 자체는 어렵지 않다. 좀 더 익숙해질필요는 있어보인다.

[Taehyeon-Kim]

• https://blog.naver.com/PostView.naver?blogId=kks227&logNo=220796029558&categoryNo=299&parentCategoryNo=0&viewDate=&currentPage=9&postListTopCurrentPage=&from=postList&userTopListOpen=true&userTopListCount=5&userTopListManageOpen=false&userTopListCurrentPage=9
• https://yy0867.github.io/posts/Dijkstra/
• https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=jh20s&logNo=221145991510

[Taehyeon-Kim]

• boj 1916 최소비용
  • https://velog.io/@j_aion/%EB%B0%B1%EC%A4%80-1753-%EC%B5%9C%EB%8B%A8%EA%B2%BD%EB%A1%9C-1necoeyq
  • https://github.com/wody-d/algorithm-study/blob/master/BOJ/1916%20%EC%B5%9C%EC%86%8C%EB%B9%84%EC%9A%A9%20%EA%B5%AC%ED%95%98%EA%B8%B0.swift

[Taehyeon-Kim]

한 3문제 정도만 풀어도 다익스트라 기본 골격은 익숙해진다.

• boj 1753 최단 경로
• boj 1916 최소 비용
• boj 1504 특정한 최단 경로