graph1 [Algorithm] Floyd-Warshall Algorithm(플로이드-와샬 알고리즘) Floyd-Warshall 알고리즘은 기존에 포스팅했던 Dijkstra 알고리즘이나 Bellman-Ford 알고리즘과 다르게, 모든 정점들 사이의 최단거리를 계산하는 알고리즘이다. 그래프의 초기 상태는 다음과 같다. 두 정점사이의 거리를 나타내는 dist 배열을 나타내보자. dist[i][j]는 정점 i에서 정점 j까지의 거리이다. dist 배열의 초기값은 i==j일때는 0으로, 정점 i와 정점 j가 연결되어있다면 두 정점을 잇는 간선의 가중치로, 두 정점이 연결되어있지 않다면 적당히 큰 수인 INF로 설정했다. 초기 dist배열의 모습은 아래와 같다. Floyd-Warshall 알고리즘의 핵심은 정점 k(14) dist[5][4]=min(dist[5][4],dist[5][2]+dist[2][4])=mi.. 2021. 8. 9. 이전 1 다음
