가장 짧은 경로를 찾는 알고리즘

1. 다익스트라 최단 경로 알고리즘

특정 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘

• 음의 간선이 없을 때 정상적으로 동작
• 1차원 리스트에 ‘각 노드에 대한 현재까지의 최단 거리’ 정보를 저장하며 리스트를 계속 갱신
• 그리디 알고리즘에 해당

1) 간단한 다익스트라 알고리즘

시간 복잡도 - $O(V^2$) v=노드의 개수

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

모든 지점에서 다른 모든 지점까지의 최단 경로를 구하는 알고리즘

• Dynamic Programming 알고리즘에 해당

점화식

• 시간 복잡도 - $O(V^3)$

d = [[float("inf") * n] for _ in range(n)]

for k in range(n):
	for a in range(n):
		for b in range(n):
			d[a][b] = min(d[a][b], d[a][k] + d[k][b]

3. 벨만 포드 알고리즘

• 매 단계마다 모든 간선의 가중치를 확인하여 최소 비용 갱신
• 음의 가중치를 가지는 그래프에서도 사용 가능