[알고리즘] 다익스트라 정의 & 문제⭐⭐

다익스트라 알고리즘은 이미 구한 답을 이용해 최소 길이를 구한다는 아이디어

---

알고리즘

red set : 실제 가장 짧은 경로가 알려진 경우

blue set : red set에 있는 노드만을 사용하여 가장 짧은 경로를 알고 있을 경우

blue set에 있는 node를 red set으로 하나씩 옮기는 것이 다익스트라!

 

처음에 red set에는 source node(=출발 노드)만을 가지고 있다.

각 round마다

• 1. blue node 중 가장 짧은 길이를 가지고 있는 노드를 선택한다.
  • 처음 시작에서 red node와 연결된 노드 중 가장 짧은 길이를 가진 노드가 나올 것이다.
• 2. 이 노드를 red set에 포함시킨다.
• 3. 이 노드와 연결된 노드의 거리를 수정한다.
  • 수정하는 대신, 새로운 거리를 가진 tuple을 heapq에 push해주어도 된다. (min-heap에서는 최단거리가 알아서 나올테니)
  • 이렇게 되면 pop할 때 특정 노드의 가장 짧은 거리가 나올 것이다.
• 모든 node가 red set으로 옮겨지면 다익스트라 알고리즘 완료

---

다익스트라 증명 (귀류법)

• A - B - C - D - E - F - G

가정 : red set에 있는 노드로만 경로(A~F)가 구성되어 있을 때 최단거리가 된다. (P이면 Q이다)

이 때, A~G까지의 최단경로는 A~F까지의 최단경로 + F~G까지의 경로이다.

 

만약 red set에 있는 노드만으로 경로가 구성되어 있을 때 최단거리가 아니라면, (P이면 ~Q이다)

blue set에 있는 노드가 중간에 A~F 사이에 들어있을 때의 거리가 red set에 있는 노드만으로 구성되어 있을 때보다 짧아야 한다.

하지만 이것은 가정에서 어긋난다.  (P이면 ~Q이다의 경우 모순 발생)

왜냐하면 가정에서 A~F까지의 경로가 red set으로 구성되어있을 때, A~G까지의 최단경로가 도출되었기 때문이다. 

 

따라서 A~G까지의 최단경로는 red set에 있는 노드로만 구성되어 있다. (따라서 P이면 Q이다 증명 완료!)

 

 

---

다익스트라 문제1

programmers.co.kr/learn/courses/30/lessons/12978?language=python3

코딩테스트 연습 - 배달

 

'''
https://programmers.co.kr/learn/courses/30/lessons/12978?language=python3
다익스트라 알고리즘 문제
'''

from collections import defaultdict
import heapq


def solution(N, road, K):
    from_to = defaultdict(list)
    for a, b, c in road:
        from_to[a].append((b, c))
        from_to[b].append((a, c))

    min_dist = {}
    start = [(0, 1)]
    while start:
        dist, src = heapq.heappop(start)
        if src not in min_dist:
            min_dist[src] = dist
            while from_to[src]:
                trg, d = from_to[src].pop()
                heapq.heappush(start, (dist + d, trg))

    answer = sum([True if dist <= K else False for src, dist in min_dist.items()])
    return answer

 

다익스트라 문제2

programmers.co.kr/learn/courses/30/lessons/49189

코딩테스트 연습 - 가장 먼 노드

# https://programmers.co.kr/learn/courses/30/lessons/49189
# 노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 
# 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.

from collections import defaultdict, deque
import heapq

def solution(n, edge):
    graph = defaultdict(list)
    for a, b in edge:
        graph[a].append(b)
        graph[b].append(a)
   
    distance = {}
    visited = []
    stack = []
    heapq.heappush(stack, (1, 1))
    while stack:
        dist, cur = heapq.heappop(stack)
        if cur not in distance:
            distance[cur] = dist
            for _next in graph[cur]:
                heapq.heappush(stack, (dist+1, _next))
    
    max_value = max(distance.values())
    return sum([True for i in distance.values() if i == max_value])

 

 

다익스트라 문제3

https://leetcode.com/problems/network-delay-time/

Network Delay Time - LeetCode

'''
https://leetcode.com/problems/network-delay-time/ (leetcode 743)

Input: times = [[2,1,1],[2,3,1],[3,4,1]], N = 4, K = 2
Output: 2

N will be in the range [1, 100].    = number of nodes
K will be in the range [1, N].      = start node
The length of times will be in the range [1, 6000].
All edges times[i] = (u, v, w) will have 1 <= u, v <= N and 0 <= w <= 100.
    - u : source
    - v : target
    - w : time
'''
from typing import List
import heapq
from collections import defaultdict


class Solution:
    def networkDelayTime(self, times: List[List[int]], N: int, K: int) -> int:
        from_to = defaultdict(list)
        for u, v, w in times:
            from_to[u].append((v, w))

        heap = []
        visited = {}
        heapq.heappush(heap, (0, K))  # distance, node
        while heap:
            dist, node = heapq.heappop(heap)
            if node not in visited:
                visited[node] = dist
                for v, w in from_to[node]:
                    heapq.heappush(heap, (dist+w, v))

        if len(visited) == N:
            return max(visited.values())
        else:
            return -1


if __name__ == "__main__":
    times = [[1, 2, 1]]
    N = 2
    K = 2

    solution = Solution()
    print( solution.networkDelayTime(times, N, K) )

 

 

다익스트라 문제4

leetcode.com/problems/cheapest-flights-within-k-stops/

Cheapest Flights Within K Stops - LeetCode

# 책 속의 해설
class Solution2:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, K: int) -> int:
        graph = defaultdict(list)
        for u, v, w in flights:
            graph[u].append((v, w))

        k = 0   # 경유 횟수
        Q = [(0, src, k)]  # (dist, src)

        while Q:
            price, node, k = heapq.heappop(Q)
            if node == dst:
                return price
            if k <= K:
                k += 1
                for v, w in graph[node]:
                    alt = price+w
                    heapq.heappush(Q, (alt, v, k))

        return -1