플로이드로셜1 [알고리즘/Python] 플로이드-워셜(Floyd-Warshall) 알고리즘 1. 플로이드-워셜(Floyd-Warshall) 알고리즘이란? 모든 최단 경로를 구하는 알고리즘 다익스트라 알고리즘과는 다르게 음의 간선도 사용할 수 있다. 2. 동작방식 모든 노드간의 최단거리를 구하는 것이므로 2차원 인접 행렬을 구성한다. 각 경로의 중간 노드를 선택하여, 거리를 더 짧게 줄이는 과정을 반복한다. 초기 그래프를 인접형렬로 나타내면 아래와 같다. INF는 해당 노드에서 특정노드까지 가는 길이 없음을 의미한다. 시작/끝 0 1 2 3 0 0 5 INF 1 1 INF 0 7 2 2 3 INF 0 INF 3 INF INF 6 0 1) 1번 노드를 중간 노드로 설정할 경우 ① 값이 변경될 경우 dist[0][2] = min(dist[0][2], dist[0][1] + dist[1][2]) = .. 2023. 4. 1. 이전 1 다음
