Floyd1

• 

  [c++] Floyd의 알고리즘 - 가중치가 다른 길찾기 문제는 다음과 같다. 가중치가 같은 최단 경로의 알고리즘으로는 BFS를 사용할 수 있지만 이 같은 경우에서는 경로마다 가중치가 다르기 때문에 BFS로 접근하면 안된다. 대신 DP 다이나믹 프로그래밍을 사용하여 부분 최적해를 구해가며 진행할 수 있겠다. 1. map만들기 우선 배열에 map을 만들어주어야 한다. 이 때 중요한 것은 갈 수 없는 방향에 대해서는 infinite한 값- 매우 큰 값으로 이루어져야 한다는 것이다. 따라서 위의 그래프를 이용해 map을 만들면 다음과 같다. int w[6][6] = { {0,0,0,0,0,0}, {0,0,1,1000,1,5}, {0,9,0,3,2,1000}, {0,1000,1000,0,4,1000}, {0,1000,1000,2,0,3}, {0,3,1000,1000,.. c++/알고리즘 2022. 5. 25.