최단경로 알고리즘

그래프상에서 가장 짧은 경로를 찾는 알고리즘

• 다익스트라 알고리즘(Dijkstra)
• 플로이드 워셜 알고리즘(Floyd-Warshall)
• 벨만-포드 알고리즘 (Bellman-Ford Algorithm)

플로이드 워셜(Floyd-Warshall)

모든 지점에서 다른 모든 지점까지의 최단 경로를 계산

단계마다 거쳐가는 노드를 기준으로 최단거리 테이블을 갱신

• 다이나믹 프로그래밍 이용 (다익스트라는 그리디와 비슷)
• 시간 복잡도 O(V^3)
• Dab = min(Dab, Dak + Dkb)

💡 문제를 통해 구현

백준 11404번 : 플로이드

import sys
sys.stdin = open('input.txt')
input = sys.stdin.readline

n = int(input())
m = int(input())
INF = int(1e9)

# 버스 이동 비용
dist = [[INF]*(n+1) for _ in range(n+1)]

for _ in range(m):
    u, v, w = map(int, input().split())
    # u -> v 노선이 여러개 존재 가능 : 최솟값으로만 저장
    if dist[u][v] > w:
        dist[u][v] = w

# 시작접 == 도착점 일 경우 비용 0으로 초기화
for i in range(1, n+1):
    for j in range(1, n+1):
        if i == j:
            dist[i][j] = 0

# 모든 거쳐가는 노드 확인 -> 최솟값으로 갱신
for k in range(1, n+1):
    for a in range(1, n+1):
        for b in range(1, n+1):
            dist[a][b] = min(dist[a][b], dist[a][k] + dist[k][b])

for i in range(1, n+1):
    for j in range(1, n+1):
        if dist[i][j] < INF:
            print(dist[i][j], end=' ')
        else:
            print(0, end=' ')
    print(end='\n')