모든 최단 경로를 구하는 알고리즘
다익스트라는 하나의 정점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘이지만,
플로이드-와샬 알고리즘은 한번 실행하여 모든 노드간 최단 경로를 구할 수 있음
하지만 시간복잡도가 O(n^3)이기 때문에, 그래프의 크기가 작아 세제곱 시간을 알고리즘에 적용해도 문제가 풀릴때만 사용할 수 있음!
모든 노드 간의 최단 거리를 구하기 위해서 2차원 인접 행렬 이용
인접 행렬은 한번에 구성되는것이 아니라 과정을 단계적으로 진행하며 최단 경로를 선택해 수정한다.
초기 그래프를 인접 행렬로 나타내면 아래와 같다.
INF
는 해당 노드에서 특정 노드까지의 경로가 존재하지 않는 경우이다.
색칠한 부분만 갱신해주면 되는데 이때 비교식이 필요하다.
A에서 B로 가는 최소 거리 와 A에서 1로 가는 거리 + 1에서 B로 가는 거리 를 비교하는 것이다.
즉, 노드1을 거쳐가는 경우가 더 빠른 경우라면 값을 갱신해주면 된다.
결과적으로 위와 같은 행렬이 만들어진다.
가지고 있는 인접 행렬을 통해서 최단거리 행렬을 초기화한다.
자기 자신으로 가는 경로의 경우에는 0
경로가 존재하지 않는 경우에는 INF
존재하는 경우에는 인접 행렬의 값을 입력한다.
for(int i = 1; i<=n; i++){
for(int j =1; j<=n; j++){
if (i == j) dist[i][j] = 0;
else if (adj[i][j]) dist[i][j] = adj[i][j];
else dist[i][j] = INF;
}
}
이때 중간 노드가 될 노드를 가장 바깥 for문의 변수로 설정한다.
i와 j를 통해 모든 노드를 확인하며 k를 중간 노드로 설정할 때와 아닐때의 값을 비교해 최단 거리로 갱신한다.
for(int k = 1; k<= n; k++){
for(int i = 1; i <= n; i++){
for(int j = 1; j<=n; j++){
dist[i][j] = Math.min(dist[i][j], dist[i][k]+dist[k][j]);
}
}
}