• 하나의 정점에서 다른 모든 정점으로 가는 최단경로를 탐색
• 즉, 정해진 출발점에서부터 도달할 수 있는 모든 도착점까지의 최단경로를 탐색하는 경우 사용
• 다만, 정점과 정점 사이의 간선이 음수인 경우에는 사용 불가

현실 세계에서는 음의 간선이 존재하지 않기 때문에 다익스트라는 인공위성, GPS 등에서 사용되는 실용적인 알고리즘입니다.

• 하나의 최단거리는 여러개의 최단거리의 합
• 다익스트라는 최단경로 탐색을 위해 이전까지 구했던 최단 거리 정보를 그대로 사용 => DP의 개념

• 1에서 3으로 이동하는 최단경로의 현재 값은 7
• 1에서 2로 이동하는 최단경로의 현재 값은 3
• 2에서 3으로 이동하는 최단경로의 현재 값은 1
• 1에서 2를 통해 3으로 이동하면, 1에서 3으로 바로 이동하는 경우보다 적은 값으로 이동 가능하기 때문에 최단경로 값이 4로 업데이트
• 즉, 특정거리까지의 최단경로를 탐색하기 위해 이전까지 구해졌던 최단거리 정보를 그대로 사용

• 출발점을 설정
• 출발점에서 부터 모든 도착점까지의 최단거리를 설정
• 방문하지 않은 노드를 모두 탐색
• 해당 노드에서부터 도달 가능한 노드의 모든 경로값 업데이트

• 1을 출발점으로 모든 노드까지의 최단경로는
  • 1에서 1까지 최단경로 => 0
  • 1에서 2까지 최단경로 => 1
  • 1에서 3까지 최단경로 => 2
  • 1에서 4까지 최단경로 => 3
  • 1에서 5까지 최단경로 => 불가(이 경우 무한대 값으로 설정)
• 즉, [0, 1, 2, 3, INF]가 출발점으로부터 모든 노드까지의 최단경로 값

• 정점 2를 탐색하는 예시

  • 1에서 2로의 이동비용 => 1
  • 2에서 4로의 이동비용 => 1
  • 1에서 2를 거쳐 4로 이동하는 비용 => 2
  • 1에서 4로 바로 이동하는 비용 => 3
  • 2를 거칠 때 비용이 바로 이동하는 비용보다 적기때문에
  • 최단거리 정보 업데이트
  • [0, 1, 2, 2, INF]

• 정점 2에서 도달 가능한 정점인 5번으로의 이동비용 탐색

  • 1에서 2로의 이동비용 => 1
  • 2에서 5로의 이동비용 => 3
  • 1에서 2를 거쳐 5로 이동하는 비용 => 4
  • 1에서 5로 바로 이동하는 비용 => 무한대
  • 2를 거칠 때 비용이 바로 이동하는 비용보다 적기때문에
  • 최단거리 정보 업데이트
  • [0, 1, 2, 2, 4]

이런 방식으로 최단거리 정보가 갱신된다.

• 다익스트라를 활용하여 연습해볼 문제

• 최소힙을 사용해야 dijkstra의 시간복잡도가 O(nlogn)
  • 단, 이 경우에도 다수의 노드가 존재할 때 각 노드들이 서로 다른 노드와 적은 수로 연결되어 있을 경우에 한해서 O(nlogn)
• Swift의 경우 간단하게 힙구조를 제공하는 라이브러리가 없기 때문에 선형탐색을 통하여 풀이 진행
• 반드시 힙 구조가 필요한 경우엔, 미리 구현해둔 heap구조를 가져와 사용(제약사항 등의 이유로 불가능할 경우는 python활용 추천)
  • 단, 아래 코드의 경우 cursor를 활용하여 removeFirst()와 같은 O(n)코드를 O(1)으로 대체
• 선형탐색을 사용하는 경우 O(n2)

func solution(_ N:Int, _ road:[[Int]], _ k:Int) -> Int {
    var graph = [[(Int, Int)]](repeating: [], count: N+1)
    
    for info in road {
        graph[info[0]].append((info[1], info[2]))
        graph[info[1]].append((info[0], info[2]))
    }
    
    var distance = [Int](repeating: Int.max, count: N+1)
    distance[1] = 0
    
    var queue = [(1, 0)], cursor = 0
    
    while cursor < queue.count {
        let now = queue[cursor]
        cursor+=1
        
        let node = now.0, dist = now.1
        
        if distance[node] < dist {
            continue
        }
        
        for nxt in graph[node] {
            let newCost = dist + nxt.1
            if distance[nxt.0] > newCost {
                distance[nxt.0] = newCost
                queue.append((nxt.0, newCost))
            }
        }
    }
    return distance.filter{$0<=k}.count
}