[Algorithm] Floyd Warshall Algorithm (플로이드 와샬 알고리즘)

 

 

지난번 배운 데이크스트라 알고리즘과 비슷하다.

 

데이크스트라는 한 정점에서 모든 노드로 향하는 가장 최단 거리를 구하는 것이고 플로이드 알고리즘은 모든 노드에서 모든 노드로 가는 최단 거리를 구한다는 점에서 약간의 차이점이 있다.

 

위 설명이 이해가 가기 어렵겠지만

 

예를 들어 문래동, 목동, 화곡동, 신대방동 이렇게 네 곳이 있을 때 문래동을 경유하는 최단 거리, 목동을 경유하는 최단거리, 화곡동을 경유하는 최단 거리, 신대방동을 경유하는 최단거리를 구한다고 생각하면 된다.

 

 

 

 

 

위 노드에 대해 코드를 작성하자면

 

 

** C++

#include <stdio.h>

int number = 4;
int INF = 1000000000;

// 자료 배열 초기화
int a[4][4] = {
	{ 0, 5, INF, 8 },
	{ 7, 0, 9, INF },
	{ 2, INF, 0, 4 },
	{ INF, INF, 3, 0 }
}; 

void floydWarshall() {
	// 결과 그래프 초기화
	int d[number][number]; 
	
	// 결과 그래프 초기화
	for (int i = 0; i < number; i++) {
		for (int j = 0; j < number; j++) {
			d[i][j] = a[i][j];
		}
	} 
	
	// k 는 거쳐가는 노드
	for (int k = 0; k < number; k++) {
		// i 는 출발 노드
		for (int i = 0; i < number; i++) {
			// j 는 도착 노드
			for (int j = 0; j < number; j++) {
				if (d[i][k] + d[k][j] < d[i][j]) {
					d[i][j] = d[i][k] + d[k][j];
				}
			} 
		} 
	} 
	
	// 결과 출력
	for (int i = 0; i < number; i++) {
		for (int j = 0; j < number; j++) {
			printf("%3d", d[i][j]);
		}
		printf("\n");
	} 
}

int main(void) {
	floydWarshall();
}

 

 

for문을 세 단계를 써서 놀랐는데 원래 그런가보다.

강의 영상에서도 for문을 세 번 쓰기 때문에 시간복잡도가 O(N^3)이라고 하였다.

 

 

 

** Javascript

 

const number = 4;
const INF = 1000000000;

// 자료 배열 초기화
let a = [
	[ 0, 5, INF, 8 ],
	[ 7, 0, 9, INF ],
	[ 2, INF, 0, 4 ],
	[ INF, INF, 3, 0 ]
]; 

function floydWarshall() {
	// 결과 그래프 초기화
    let d = [];
    for (let i = 0; i < number; i++) {
        const arr = [0, 0, 0, 0];
        d.push(arr);
    }
	
	// 결과 그래프 초기화
	for (let i = 0; i < number; i++) {
		for (let j = 0; j < number; j++) {
			d[i][j] = a[i][j];
		}
	} 
	
	// k 는 거쳐가는 노드
	for (let k = 0; k < number; k++) {
		// i 는 출발 노드
		for (let i = 0; i < number; i++) {
			// j 는 도착 노드
			for (let j = 0; j < number; j++) {
				if (d[i][k] + d[k][j] < d[i][j]) {
					d[i][j] = d[i][k] + d[k][j];
				}
			} 
		} 
	} 
	
	// 결과 출력
	for (let i = 0; i < number; i++) {
		console.log(d[i]);
	} 
}

floydWarshall();

 

 

** Python

 

number = 4
INF = 1000000000

## 자료 배열 초기화
a = [
    [0, 5, INF, 8],
    [7, 0, 9, INF],
    [2, INF, 0, 4],
    [INF, INF, 3, 0]
]

def floyd_warshall():
    ## 결과 그래프 초기화
    d = []
    for i in range(number):
        d.append([0,0,0,0])
    ## 결과 그래프 초기화
    for i in range(number):
        for j in range(number):
            d[i][j] = a[i][j]
    ## k는 거쳐가는 노드
    for k in range(number):
        ## i는 출발 노드
        for i in range(number):
            ## j는 도착 노드
            for j in range(number):
                if d[i][k] + d[k][j] < d[i][j]:
                    d[i][j] = d[i][k] + d[k][j]
    ## 결과 출력
    for i in range(number):
        print(d[i])
        
if __name__ == "__main__":
    floyd_warshall()

 

 

** Java

 

public class Main
{
    private static int number = 4;
    private static int INF = 1000000000;
    private static int a[][] = {
    	{ 0, 5, INF, 8 },
    	{ 7, 0, 9, INF },
    	{ 2, INF, 0, 4 },
    	{ INF, INF, 3, 0 }
    };
    private static void floydWarshall() {
        // 결과 그래프 초기화
    	int d[][] = new int[number][number]; 
    	
    	// 결과 그래프 초기화
    	for (int i = 0; i < number; i++) {
    		for (int j = 0; j < number; j++) {
    			d[i][j] = a[i][j];
    		}
    	} 
    	
    	// k 는 거쳐가는 노드
    	for (int k = 0; k < number; k++) {
    		// i 는 출발 노드
    		for (int i = 0; i < number; i++) {
    			// j 는 도착 노드
    			for (int j = 0; j < number; j++) {
    				if (d[i][k] + d[k][j] < d[i][j]) {
    					d[i][j] = d[i][k] + d[k][j];
    				}
    			} 
    		} 
    	} 
    	
    	// 결과 출력
    	for (int i = 0; i < number; i++) {
    		for (int j = 0; j < number; j++) {
    			System.out.printf("%3d", d[i][j]);
    		}
    		System.out.printf("\n");
    	}
    }
	public static void main(String[] args) {
		floydWarshall();
	}
}