플로이드 워셜 알고리즘 정리

확실히 다익스트라 알고리즘에 비하면 쉽긴하다.

다익스트라가 음수는 되지 않는다는 문제점이 있었는데 이걸로 사용하면 될것 같다,

플로이드 워셜의 핵심 코드는

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]);
                }
            }
	}

이런식으로 생겼다.

현재 k는 무엇을 뜻하며,
i는 무엇을 뜻하며,
j는 무엇일까?

잘 모르니까 그냥 해보자. 

k	i	j		k	i	j
1	1	1		1	3	1
1	1	2		1	3	2
1	1	3		1	3	3
1	1	4		1	3	4
1	2	1		1	4	1
1	2	2		1	4	2
1	2	3		1	4	3
1	2	4		1	4	4

 

아직도... 솔직히 잘 모르겠다. k가 단계라고 하는데... 그것도 잘 모르겠구...

그래서 그림을 그려보자.

 

즉, 그래프가 양방향일 때 가능하다는 이야기가 된다.

그러면 단방향은 될까?

이건 좀더 생각을 해야할 것 같다.

 

결국, 다익스트라 알고리즘은 각 노드를 돌면서 최단 경로를 찾는 반면,

플로이드 워셜 알고리즘은 서로의 값을 교환해서 더 짧은 경로를 찾는다는 특징을 가지고 있다.