플로이드 와샬 알고리즘(Floyd Warshall Algorithm)

플로이드 와샬 알고리즘이란? '모든 정점'에서 '모든 정점'으로의 최단 경로를 구하는 알고리즘 다익스트라 알고리즘과의 차이점 다익스트라는 하나의 정점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘으로 가장 적은 비용을 하나씩 선택한다. 하지만 플로이드 와샬 알고리즘은 기본적으로 '거쳐가는 모든 정점'을 기준으로 알고리즘을 수행한다. 알고리즘 위와 같은 그래프가 존재한다고 할 때, D는 각각의 정점이 다른 정점으로 가는 비용을 이차원 형태로 저장해놓은 것이다. 처음에는 위와 같은 상태이다. 이때 무한대는 이동하는 경로가 없다는 뜻이고 자신 자신의 비용은 0이다. D[x][y] = x에서 y로 가는 최소 비용을 의미한다. 거쳐가는 정점을 K라고 하자. X에서 Y로 가는 최소 비용과 X에서 노드 K로 ..
Algorithm 2021. 7. 27. 00:08
1
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
TAG more
«   2024/12   »
일 월 화 수 목 금 토
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31
글 보관함