플로이드 와샬 알고리즘

다익스트라와 벨만-포드 알고리즘은 시작점이 정해져 있어서 모든 쌍에 대한 최단 경로를 알아낼 수 없었습니다. 물론, 단일 시작점 알고리즘을 여러 번 돌린다면 모든 쌍에 대한 최단 경로를 찾아낼 수 있지만, 시간 복잡도와 알고리즘 구현 측면에서 한번만 실행해도 되는 플로이드-와샬 알고리즘이 더 적합한 선택일 것입니다. 2020/08/31 - [알고리즘] - 다익스트라 알고리즘 2020/09/07 - [알고리즘] - 벨만포드 알고리즘 2020/09/07 - [알고리즘] - SPFA (Shortest Path Faster Algorithm) 플로이드-와샬 알고리즘은 벨만-포드 알고리즘과 동일하게 음수 가중치가 있어도 사용 가능합니다. 플로이드-와샬 알고리즘의 동작 과정을 알아봅시다. 먼저, 모든 쌍의 최단 경..
알고리즘 2020. 9. 9. 01:55
1