최단 경로 문제

• 가중 간선
  정점 u에서 정점 v까지의 경로 중에 경로의 값이 가장 작은 경로
• 가중 경로

문제의 구분

• 시작점과 도착점의 수에 따라 다음과 같이 구분
  • 계산양의 차이
  • single-source & single-destination
  • Single-source
  • Single-destination
  • All pairs

다익스트라 알고리즘

• 하나의 시작점에서 하나의 도착점을 가는 최단 경로를 찾는 알고리즘
• 간선이 음의 값을 가져서는 안 된다.
  

정리

큐에 그래프의 정점들을 전부 집어넣고 최소값을 골라 그 정점에서 갈 수 있는 간선들을 찾아 값울 구하여 큐에 저장된 정점들의 값과 갈 수 있는 값을 비교하여 더 적은 값을 집어 넣고 그 중 가장 작은 값을 가진 정점에서 다시 반복한다.

---

최단경로 문제를 해결하는 다익스트라 알고리즘 정점을 하나씩 추가하면서 완화를 통해 새로운 경로에서 경로값을 계산하여 새로운 경로를 추가하여 최단 경로를 찾는 알고리즘이다.

수행시간 분석

• 배열로 구현할 경우 :$O(V^2)$
• 힙구조로 구현한 경우 : $O(VlgV+ElgV)$
• 피보나치 힙으로 구현한 경우: $O(VlgV+E)$

코드

import heapq

queue = []

mygraph = {
    'A': {'B': 8, 'C': 1, 'D': 2},
    'B': {},
    'C': {'B': 5, 'D': 2},
    'D': {'E': 3, 'F': 5},
    'E': {'F': 1},
    'F': {'A': 5}
}

def dijksta(graph,start):

    distances = {node:float('inf') for node in graph}
    distances[start] = 0

    queue = []

    heapq.heappush(queue,[distances[start],start])

    while queue:
        current_distance,current_node = heapq.heappop(queue)

        if distances[current_node] < current_distance:
            continue
        for adjacent, weight in graph[current_node].items():
            distance = current_distance + weight

            if distance < distances[adjacent]:
                distances[adjacent] = distance
                heapq.heappush(queue,[distance,adjacent])

    return distances

print(dijksta(mygraph,'A'))