플로이드 와샬 알고리즘1 최단거리구하기_플로이드 와샬(Floyd Warshall) 알고리즘 플로이드 알고리즘에 대한 이해 - 플로이드 알고리즘이란, 그래프의 모든 정점 쌍 사이의 최단 거리를 구하는 알고리즘이다. - 모든 정점 쌍에 대한 2차원 표를 채우는 과정으로 진행된다. V(노드의 개수) = 6, E(간선의 개수) = 7 인 다음과 같은 그래프에서 모든 정점 쌍 사이의 최단 거리를 구해보자. 먼저, 아무 정점도 거치지 않았을 때 정점 i와 정점 j 사이의 최단 거리로 표를 채운다. 예를 들어, 정점 3과 정점 6은 아무 정점도 거치지 않았을 때 거리가 8이다. 물론, 3 -> 2 -> 5 -> 6 으로 이동하는 경우 더 작은 거리(7)로 도달할 수 있으나, 가장 처음에는 다른 정점을 거치는 경우를 제외하고 직행으로 연결하였을 때의 최단 거리만 표에 기록한다. int V, E; vector.. 2022. 3. 7. 이전 1 다음