반응형
플로이드 와샬
-
[알고리즘] Floyd Warshall알고리즘 2021. 12. 4. 21:21
이 글은 혼자 학습한 내용을 바탕으로 작성되었습니다. 틀리거나 잘못된 정보가 있을 수 있습니다. 댓글로 알려주시면 수정하도록 하겠습니다. 1. floyd warshall 알고리즘이란? 음의 사이클이 없는 그래프에서 모든 정점에서 다른 모든 정점으로의 최단 거리를 구하는 알고리즘 이며 음의 간선이 존재하여도 최단 거리를 구할 수 있습니다. 또한 floyd warshall 알고리즘은 경유하는 정점을 기준으로 최단거리를 구해나가는 알고리즘 입니다. 2. Dijkstra VS floyd warshall floyd warshall알고리즘과 Dijkstra 알고리즘은 유사 하지만 조금씩의 차이점이 있습니다. Dijkstra는 특정 정점에서의 최단 거리를 구하는 알고리즘이고 floyd warshall은 모든 정점의 ..