다익스트라 vs 플로이드 와샬 차이점

플로이드 와샬을 다익스트라 알고리즘을 기반으로 하지만, 차이점이 있다면

다익스트라는 특정 정점에서 방문하지 않은 다른 모든 정점까지의 최단 거리를 구한다면, 플로이드 와샬은 모든 정점에서 모든 정점에 이르는 최단 거리를 구한다. 어떤 노드를 거치느냐에 따라 최단거리가 달라지기 때문에 플로이드 와샬에서 중요한 핵심은 경유하는 노드이다!

다익스트라 1. 특정 정점start에서 가장 최단거리의 노드j를 찾는다. 2. 특정 정점start에서 방문하지 않은 노드end를 차례로 방문하여 기존의 Dist[start][end]와 Dist[start][j] + Dist[j][end] 중 최솟값을 구한다. => 시작점이 start로 고정되어 있기 때문에 거리를 저장하는 배열은 1차원 배열로 나타낼 수 있다! => Dist[end] vs Dist[j] + Arr[j][end] //Arr은 주어지는 가중치 정보

플로이드 와샬 : 모든 정점에서 시작해 모든 정점에 도착하는 최단 거리를 구한다!=> 경유지가 중요! 1. 3중 for문을 구성하여 각각의 노드가 경유지가 됐을 때를 고려한다.