그래프 최단 거리 구하기 알고리즘(다익스트라 알고리즘, 플로이드-워셜 알고리즘)

다익스트라 알고리즘 최단 경로 찾기 알고리즘의 하나로, 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단경로를 알려준다 단, 음의 간선이 있을 경우는 사용할 수 없으며, 하나의 최단 거리를 구할 때, 그 이전까지 구했던 최단 경로의 정보를 그대로 사용하기 때문에 DP 문제라고 볼 수 있다. 원리 특정한 하나의 정점을 잡고, 그 정점과 이웃한 정점들의 비용을 각각 확인하여 그 후, 이웃한 정점들 중 가장 비용이 적게 드는 정점을 기준으로 다시 한 번 확인한다. (직접 이웃한 정점으로 가는 것보다, 이웃한 다른 정점을 거쳐서 가는 것이 더 적은 비용이 들수도 있기 때문에) 이걸 반복하면서, 현재까지 알고 있던 최단 경로를 계속 갱신해나가면 된다 1. 출발 노드와, 도착 노드를 설정 2. 알고 있는 모든 ..

2021.03.23