플로이드 워셜 알고리즘 개요플로이드 워셜 알고리즘은모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산한다다익스트라 알고리즘과 마찬가지로, 단계별로 거쳐가는 노드를 기준으로 알고리즘을 수행한다. 그러나, 아래 두 가지에서 다익스트라와 차이가 있다. 다익스트라 알고리즘은 한 시작점에서 다른 정점까지의 최단 거리를 구하는데 반해 플로이드 알고리즘은 모든 정점 쌍에 대해서 둘 사이의 최단 거리를 구할 수 있다. 음의 가중치를 가지는 그래프에서도 쓸 수 있다플로이드 알고리즘은 2차원 테이블에 최단 거리 정보를 저장한다. 플로이드 워셜 알고리즘각 단계마다 특정 한 노드 k를 거쳐가는 경우를 확인한다.a에서 b로 가는 최단거리보다, a에서 k를 거쳐 b로 가는 거리가 더 짧은지 검사한다.점화식은 다음과 같다...

다익스트라 알고리즘다익스트라 알고리즘은 최단경로를 구하는 알고리즘 중 하나이다.다익스트라 알고리즘을 사용하면 하나의 노드에서 다른 모든 노드까지의 거리를 구할 수 있다. 다익스트라 알고리즘 원리다익스트라 알고리즘은 아래의 두 문장으로 정리될 수 있다.최단거리를 구할 노드에서 시작하여, 거리가 입력된 노드 중 최단거리가 가장 작은 노드를 돌아가며 선택한다.노드를 돌아가면서, 더 거리가 짧다면 값을 갱신한다. (a) 노드 0에서 거리를 기록한 후, 가장 가까운 노드인 1번노드를 선택한다(b) 선택된 1번노드를 기준으로, 거리가 최소가 되도록 갱신한다. 0번노드에서 3번 노드로 바로 갈 경우, 거리가 무한대이지만, 1번노드를 거쳐가면 거리가 6이므로 3번노드까지의 거리를 6으로 갱신한다. 가장 가까운 노드는 ..