플로이드에서 하나의 정점만 살펴본다고 할 때

플로이드에서 '하나의 정점만 살펴본다고 할 때'의 의미는 시작점이 하나일 때를 말하는 것이다. 시작점이 하나일 때는 전에 벨만포드 혹은 다익스트라로 해결했다

 

그러면 플로이드에 하나의 정점만 살펴본다고 하면 시간복잡도를 줄일 수 있나?

줄일 수 없다. 왜냐하면 플로이드 알고리즘은 그 자체가 다이나믹 프로그래밍의 성질인 Optimal Substructure로 인해서 반드시 모든 정점을 따져봐야만 한다