728x90 Floyd Warshall1 [C++] 플로이드 와샬(Floyd Warshall) 알고리즘 개념 플로이드 와샬 알고리즘이란? 다익스트라 알고리즘이 하나의 정점에서 출발했을 때 다른 모든 정점으로의 최단 경로를 구하는 알고리즘이라면 플로이드 와샬 알고리즘은 모든 정점에서 모든 정점으로의 최단 경로를 구하는 알고리즘입니다. 핵심 아이디어는 거쳐가는 정점을 기준으로 최단 거리를 구하는 것입니다. 예시코드 int node[n + 1][n + 1];//입력받기 int dp[n + 1][n + 1];//다이나믹 프로그래밍 void floydWarshall(int n) { //그래프 초기화 for (int i = 1; i 2021. 8. 24. 이전 1 다음 728x90