다익스트라(dijkstra)

출처: https://t1.daumcdn.net/cfile/tistory/277CC93A54C0ABE80A

📔 다익스트라(dijkstra) 란

• 다익스트라를 들어가기 전에... 최단 경로란
  • 간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중 간선의 가중치의 합이 최소인 경로
  • 간선의 가중치가 균일(1)할 경우 BFS를 사용
• 음의 가중치를 허용하지 않음
• 하나의 시작 정점에서 끝 정점까지의 최단경로
  • 시작 정점에서 거리가 최소인 정점을 선택해 나가면서 최단 경로를 구하는 방식이다.
  • 시작 정점(s) 에서 끝 정점(t) 까지의 최단 경로에 정점 x 가 존재한다.
  • 이때, 최단 경로는 s 에서  x 까지의 최단경로와 x 에서 t 까지의 최단경로로 구성된다.
  • 탐욕 기법을 사용한 알고리즘으로 MST의 프림 알고리즘과 유사하다.
• 아래 코드의 경우 시간복잡도는 O(N^2) 이다.
• 만약 우선순위큐를 이용하게 된다면 O(NlogN) 으로 시간복잡도를 줄일 수 있다.

📔 다익스트라(dijkstra) 구현

V, E = 6, 11
edges = [
    [0, 1, 3],
    [0, 2, 5],
    [1, 2, 2],
    [1, 3, 6],
    [2, 1, 1],
    [2, 3, 4],
    [2, 4, 6],
    [3, 4, 2],
    [3, 5, 3],
    [4, 0, 3],
    [4, 5, 6]
]

# 인접리스트 만들기
adj = {x: [] for x in range(V)}
for edge in edges:
    s, e, c = edge
    adj[s].append([e, c])

# dist, visited
dist = [float('inf')] * V
visited = [False] * V

# 시작점 선택, 모든 정점 선택
dist[0] = 0
cnt = 0
while cnt < V:
    # dist가 최소인 정점 찾기
    min_dist = float('inf')
    u = -1
    for i in range(V):
        if not visited[i] and dist[i] < min_dist:
            min_dist = dist[i]
            u = i

    # 정점을 하나 선택
    visited[u] = True

    # 간선 완화
    for w, cost in adj[u]:  # 도착정점, 가중치
        if dist[u] + cost < dist[w]:
            dist[w] = dist[u] + cost
    cnt += 1

print(dist)