최단 경로 알고리즘

1. 다익스트라 알고리즘

   한 지점에서 다른 특정 지점까지의 최단 경로

• 그래프에서 여러 개의 노드가 있을 때 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로 구해줌
• 그리디 : 매번 가장 비용이 적은 노드를 선택
• 각 노드에 대한 현재까지의 최단 거리 정보를 리스트에 저장하여 계속 갱신
  -1. 출발 노드를 설정한다.
  -2. 최단 거리 테이블을 초기화한다.
  -3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.
  -4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.
  -5. 위의 3과 4를 반복한다.
• 간단한 다익스트라 알고리즘

# 무한대 설정
INF = int(1e9)

n, m = map(int, input().split())
start = int(input())
g = [[] for _ in range(n+1)]
check = [False] * (n+1)
# 각 노드를 무한대로 초기화
d = [INF] * (n+1)

# 간선의 정보 입력 받기
for _ in range(m):
    a, b, c = map(int, input().split())
    g[a].append((b, c))

# 방문하지 않은 노드 중 최단거리가 가장 짧은 노드를 찾음
def get_smallest_node():
    min_value = INF
    index = 0
    for i in range(1, n+1):
        if d[i] < min_value and not check[i]:
            min_value = d[i]
            index = i
    return index

# 다익스트라
def dijkstra(start):
    # 시작 노드는 거리 0으로 설정
    d[start] = 0
    # 시작 노드 방문
    check[start] = True
    # 시작노드와 연결된 노드들 거리 갱신
    for j in g[start]:
        d[j[0]] = j[1]
    # 시작노드 제외 나머지에 대해 반복
    for i in range(n-1):
    	# 방문하지 않은 노드 중 최단거리가 가장 짧은 노드 선택, 방문처리
        now = get_smallest_node()
        check[now] = True
        # 선택 노드와 연결된 노드들 최단거리 갱신
        for j in g[now]:
            cost = d[now] + j[1]
            if cost < d[j[0]]:
                d[j[0]] = cost

dijkstra(start)

for i in range(1, n+1):
    if d[i] == INF:
        print("infinity")
    else:
        print(d[i])

• 개선된 다익스트라 알고리즘
  • 최단거리가 가장 짧은 노드를 찾기 위해 힙 이용

import heapq
INF = int(1e9)

n, m = map(int, input().split())
start = int(input())
g = [[] for _ in range(n+1)]
d = [INF] * (n+1)

for _ in range(m):
    a, b, c = map(int, input().split())
    g[a].append((b, c))

def dijkstra(start):
    q = []
    # 큐에 시작노드 넣어준다
    heapq.heappush(q, (0, start))
    d[start] = 0
    # 큐가 빌 때까지
    while q:
    	# 최단거리가 가장 짧은 노드 꺼냄
        dist, now = heapq.heappop(q)
        # 만약 이미 방문한 적 있는 노드라면 다음 꺼내기 위해 continue
        if d[now] < dist:
            continue
        # 현재 노드와 연결된 노드들 확인해서
        for i in g[now]:
            cost = dist + i[1]
            # 현재 노드 거쳐 다른 노드 갈 때 더 짧은 경우 갱신
            if cost < d[i[0]]:
                d[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))

dijkstra(start)

for i in range(1, n+1):
    if d[i] == INF:
        print("infinity")
    else:
        print(d[i])

https://programmers.co.kr/learn/courses/30/lessons/12978

2. 플로이드 워셜 알고리즘

   모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구할 때

• 다익스트라 / 플로이드 워셜 : 거쳐 가는 노드 기준
• 플로이드 워셜 : 매번 방문하지 않은 노드 중 최단 거리를 갖는 노드를 찾을 필요가 없다. 현재 노드를 거쳐가는 모든 경로를 고려한다.
• 다이나믹 프로그래밍
• 각 단계에서 해당 노드를 거쳐가는 경우를 고려한다.
  • ex. 1번 노드 확인 시 1번 노드를 거쳐 지나가는 모든 경우의 수 고려
    • (A -> 1번 -> B) 가는 비용 확인 후 최단 거리 갱신
    • 현재 노드 제외 n-1 개의 노드에 대해 반복

INF = int(1e9)

n = int(input())
m = int(input())

g = [[INF] * (n+1) for _ in range(n+1)]

# 자기 자신으로 가는 경로
for a in range(1, n+1):
    for b in range(1, n+1):
        if a == b:
            g[a][b] = 0

for _ in range(m):
    a, b, c = map(int, input().split())
    g[a][b] = c
    
# 최단거리 갱신 점화식    
for k in range(1, n+1):
    for a in range(n+1):
        for b in range(n+1):
            g[a][b] = min(g[a][b], g[a][k]+g[k][b])
            
for a in range(1, n+1):
    for b in range(1, n+1):
        if g[a][b] == INF:
            print("infinity", end = " ")
        else:
            print(g[a][b], end = " ")
    print()

https://programmers.co.kr/learn/courses/30/lessons/49189
https://programmers.co.kr/learn/courses/30/lessons/72413
https://programmers.co.kr/learn/courses/30/lessons/42861
https://programmers.co.kr/learn/courses/30/lessons/49191
https://programmers.co.kr/learn/courses/30/lessons/1844
https://www.acmicpc.net/workbook/view/1711
https://www.acmicpc.net/workbook/view/3581