[알고리즘] 최단 경로

🌏 최단경로

간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중에 간선의 가중치의 합이 최소인 경로

• 하나의 시작 정점에서 끝 정점까지의 최단경로
  - 다익스트라(dijkstra) 알고리즘
  - 벨만-포드(Bellman-Ford) 알고리즘
• 모든 정점들에 대한 최단경로
  - 플로이드-워샬(Floyd-Warchall) 알고리즘

---

최단 거리 문제 유형

정점 사이의 거리가 최단인 경로 찾기

1. 특정 지점 -> 도착 지점까지의 최단 거리 : 다익스트라
2. 가중치에 음수가 포함되어 있음 : 밸만포드
3. 여러 지점 -> 여러 지점까지의 최단 거리
   • 여러 지점 모두 다익스트라 돌리기 : 시간복잡도 계산 잘하기
   • 플로이드-워샬

---

다익스트라(dijkstra) 알고리즘

시작 정점에서 거리가 최소(누적 거리)인 정점을 선택해 나가면서 최단 경로를 구하는 방식

• 시작정점(s)에서 끝정점(t)까지의 최단 경로에 정점 x가 존재한다
• 이때, 최단경로는 s에서 x까지의 최단경로와 x에서 t까지의 최단경로 구성
• 탐욕 기법을 사용한 알고리즘으로 MST의 프림 알고리즘과 유사하다

1. 누적거리를 계속 저장
2. 우선순위 큐 

# 누적거리 + 누적거리 기준 idq(우선순위 큐) 구현
# 갈 수 있는 경로 중 누적거리가 가장 짧은 것부터 선택
'''
6 8
0 1 2
0 2 4
1 2 1
1 3 7
2 4 3
3 4 2
3 5 1
4 5 5
'''
import heapq

n, m = map(int, input().split())
# 인접리스트
graph = [[] for _ in range(n)]
for _ in range(m):
    f, t, w = map(int, input().split())
    graph[f].append([t, w])

# 누적거리 계속 저장할 배열
INF = int(1e9) # 최대값으로 1억
distance = [INF] * n

def dijkstra(start): # 시작점
    # 우선순위 큐
    pq = []
    heapq.heappush(pq, (0, start))
    distance[start] = 0 # 시작점 누적거리의 합을 0으로 지정

    while pq:
        # 현 시점에서 누적 거리가 가장 짧은 노드에 대한 정보 꺼내기
        dist, now = heapq.heappop(pq)

        # 이미 방문한 지점 + 누적 거리가 더 짧게 방문한 적이 있다면 pass
        if distance[now] < dist:
            continue

        # 인접 노드 확인
        for next in graph[now]:
            next_node = next[0]
            cost = next[1]

            # next_node 로 가기 위한 누적 거리
            new_cost = dist + cost

            # 누적 거리가 기존보다 크다면
            if distance[next_node] <= new_cost:
                continue

            # 누적 거리가 더 짧다면 바꿔줌
            distance[next_node] = new_cost
            heapq.heappush(pq, (new_cost, next_node))

dijkstra(0)
print(distance)

• 변수명 주의!!
• 리스트와 값이 들어갈 변수 이름은 다르게 해준다