Floyd-Warshall algorithm
목차 (클릭 시 이동) Floyd-Warshall 알고리즘 Floyd-Warshall 알고리즘은 음의 순환이 없는 가중치 그래프에서 정점들 간 최단 거리를 찾는 알고리즘이다. 음의 가중치를 갖는 그래프에도 적용 가능하다. 한 번의 수행으로 각 정점들 서로 간의 최단 거리를 찾는다. 구현 알고리즘을 실행하기 위해 인접 리스트를 2차원 배열로 작성하면 편하다. int main() { int n = 5; // # of vertices int edges[][3] = { {1, 2, 2}, {2, 3, 6}, {3, 2, 7}, {4, 3, 1}, {4, 5, 3}, {5, 1, 1}, {5, 2, 4}, }; // n + 1 to match the index with the number of vertex vec..
