그래프 최단 거리 구하는 알고리즘
1. 다익스트라(Dijkstra)
2. 벨만-포드(Bellman-Frod)
3. 플로이드-와샬(Floyd-Wrasahll)
플로이드-와샬(Folyd-Warshall) 알고리즘
O(n^3)
경유지 k
, 출발 정점 i
, 도착 정점을 j
라고 하자. 그래프는 graph
라는 이중 배열에 저장되어있다.
graph[i][j]
는 지금까지 i
에서 j
까지 가는 최단 거리이다.
graph[i][k] + graph[k][j]
는 i
에서 j
까지 가는데 k
를 거쳐서 가는 거리이다.
만약, graph[i][j] > graph[i][k] + graph[k][j]
면 i
부터 j
까지 가는데 k
를 거쳐서 가는 것이 더 최단 거리이다. 따라서 graph[i][j]
는 graph[i][k] + graph[k][j]
로 갱신해준다.
graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
예시
다음과 같은 가중치 방향 그래프가 있다. 이중 배열로 그래프를 표현했으며 이 이중배열을 graph
라 하자.
1) 1번 정점를 경유하여 가는 경우를 살필 것이다. 1번 정점에서 출발하는 경우와 도착하는 경우를 빼고 나머지 정점에 대해 살펴본다.
graph[3][2]
= 11로 값 변경
① graph[3][2]
= 13이다.
② graph[3][1]
+ graph[1][2]
= 1 + 10 = 11이다.
① > ② 이므로 graph[3][2]
값을 11로 변경해준다.
graph[4][2]
= 11로 값 변경
① graph[4][2]
= 무한이다.
② graph[4][1]
+ graph[1][2]
= 8 + 10 = 11이다.
4에서 1을 경유하고 2로 갈 수 있으므로 graph[4][2]
값을 18로 변경해준다.
graph[4][3]
= 13로 값 변경
① graph[4][3]
= 무한이다.
② graph[4][1]
+ graph[1][3]
= 8 + 5 = 13이다.
4에서 1을 경유하고 3으로 갈 수 있으므로 graph[4][3]
값을 13으로 변경해준다.
2) 2번 정점를 경유하고 가는 경우를 살펴본다.
graph[5][3]
= 13로 값 변경
① graph[5][3]
= 무한이다.
② graph[5][2]
+ graph[2][3]
= 31 + 2 = 33이다.
5에서 2을 경유하고 3으로 갈 수 있으므로 graph[5][3]
값을 33으로 변경해준다.
graph[1][3]
값 변경 없음
① graph[1][3]
= 5이다.
② graph[1][2]
+ graph[2][3]
= 10 + 2 = 12이다.
① < ② 이므로 graph[1][3]
값은 그대로이다.
이런 방식으로 정점 5까지 반복해준다.
3) 정점 3 경유
4) 정점 4 경유
5) 정점 5 경유
최종) 플로이드-와샬 알고릴즘 수행
플로이드 알고리즘
//이중 배열에 저장된 그래프, 정점의 개수 넘겨줌
public static void floyd(int[][] graph, int n) {
// 경유지
for (int k = 1; k <= n; k++) {
// 출발지
for (int i = 1; i <= n; i++) {
//도착지
for (int j = 1; j <= n; j++) {
graph[i][j] = Math.min(graph[i][j], graph[i][k]+graph[k][j]);
}
}
}
}
전체 코드
public class Main {
static final int INF = 1000000000;
public static void floyd(int[][] graph, int n) {
// 경유지
for (int k = 1; k <= n; k++) {
// 출발지
for (int i = 1; i <= n; i++) {
//도착지
for (int j = 1; j <= n; j++) {
graph[i][j] = Math.min(graph[i][j], graph[i][k]+graph[k][j]);
}
}
}
//출력
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if(graph[i][j] == INF) System.out.print(0+" ");
else System.out.print(graph[i][j]+" ");
}
System.out.println();
}
}
public static void main(String[] args) throws IOException {
//그래프 입력 받기
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
// 정점의 개수, 간선의 개수
int n = Integer.parseInt(bf.readLine());
int m = Integer.parseInt(bf.readLine());
int[][] graph = new int[n + 1][n + 1];
for (int i = 0; i < graph.length; i++) {
for (int j = 0; j < graph.length; j++) {
if(i == j) continue;
graph[i][j] = INF;
}
}
StringTokenizer st;
for (int i = 0; i < m; i++) {
st = new StringTokenizer(bf.readLine());
int v = Integer.parseInt(st.nextToken());
int w = Integer.parseInt(st.nextToken());
int cost = Integer.parseInt(st.nextToken());
graph[v][w] = cost;
}
//플로이드 알고리즘 수행
floyd(graph, n);
}
}
입력
5
9
1 2 10
1 3 5
2 3 2
3 1 1
3 2 13
4 1 8
4 5 3
5 4 9
5 2 31
출력 결과
0 10 5 0 0
3 0 2 0 0
1 11 0 0 0
8 18 13 0 3
17 27 22 9 0