[알고리즘] 플로이드-와샬 알고리즘 (Floyd-Warshall Algorithm) - JAVA / 자바

플로이드-와샬(Floyd-Warshall Algorithm)

  = 플로이드 알고리즘, 로이-와샬 알고리즘, 로이-플로이드 알고리즘, WFI 알고리즘

  : 음의 사이클이 없는 가중 그래프에서 최단 경로를 찾는 알고리즘이다

 

특징

  ① 음의 간선이 있는 가중 그래프에서 사용 가능 (≠ 다익스트라 알고리즘(Dijkstra Algorithm))

---

알고리즘

① V1부터 Vn까지 연결된 간선 인접 행렬에 저장
② 경유하는 정점으로 V1~Vn을 설정 (k)
③ 시작 정점(i)을 V1~Vn, 도착정점(j)을 V1~Vn으로 하는 경우 모두 탐색
    이때, <V1, V2>의 값이 <V1, Vk> + <Vk, V2>보다
      1. 작거나 같으면 그냥 넘어감
      2. 크면 값 대체

Before graph	V1	V2	V3	V4	After graph	V1	V2	V3	V4
V1	0	INF	2	5	Floyd - Warshall	0	3	2	3
V2	INF	0	3	INF		INF	0	3	4
V3	INF	1	0	1		INF	1	0	1
V4	INF	INF	INF	0		INF	INF	INF	0

---

의사 코드 (Pseudo Code)

Floyd-Warshall(graph)
	n ← 정점의 개수;
    for(k ← 0; k<n; k ← k+1) do {
        for(i ← 0; i<n; i ← i+1) do {
            for(j ← 0; j<n; j ← j+1) do {
                graph[i][j] ← min(graph[i][j], graph[i][k]+graph[k][j]);
            }
        }
    }
end Floyd-Warshall()

---

Java 코드 구현

public static void FloydWarshall(int graph[][]) {
	for(int k=0; k<n; k++)
		for(int i=0; i<n; i++)
			for(int j=0; j<n; j++)
				graph[i][j] = Math.min(graph[i][j], graph[i][k]+graph[k][j]);
}

시간복잡도 = O(V^3)

---

대표적인 플루이드-와샬 알고리즘 사용 예

 - 가중 그래프에서의 최단 경로 탐색

 - 그 외...