Floyd-Warshall2 [BOJ] 백준 11404 - 플로이드 2021.08.09 - [Algorithm/Theory] - [Algorithm] Floyd-Warshall Algorithm(플로이드-와샬 알고리즘) 문제 링크 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 도시(정점), 버스(간선), 버스의 비용(가중치)를 갖는 그래프에서, 모든 도시(정점) 의 쌍 (A,B)에 대해 A에서 B로 가는데 필요한 최소 비용을 구하는 문제이다. 문제의 제목과 같이 Floyd-Warshall 알고리즘으로 해결 할 수 있었다. 해당 알고리즘은 아래 링크에서 확인할 수 있다. 202.. 2021. 8. 9. [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 다음
