다익스트라, 플로이드와샬 알고리즘

1. 다익스트라 알고리즘

다익스트라 - 위키백과  

방문 순서 : 1 - 2 - 3 - 6 - 5 - 4

 

어떤 노드를 먼저 방문할거냐?

distance가 가장 작은 노드부터 방문.

=> 우선순위큐 필요함.

 

우선순위큐가 없어도 문제해결은 가능하지만 비효율적.

우선순위큐를 안쓰면 시간초과인 문제도 있었던 것 같음.

 

간선이 적을 경우 노드 간의 거리를 배열로 구현

간선이 많을 경우 리스트로 구현

   

계속하는 실수

다익스트라 문제를 볼 때마다 프림 알고리즘이 떠오른다.

그래서 PriorityQueue 우선순위를 간선의 비용으로 하더라.

어떤 Node를 방문할지에 대해 각 Node의 거리에 따른 우선순위로!!

   

2. 플로이드 와샬 알고리즘

3중 for문

이때까지 플로이드 와샬로 풀었던 문제는 1~2개 정도인 것 같다.

다익스트라는 특정 노드에서 출발하여 다른 노드까지의 최단거리를 구하는 알고리즘이었다면

플로이드 와샬은 모든 노드와 노드 사이의 최단거리를 구하는 알고리즘.

 //플로이드 와샬
    for (int k = 0; k < N; k++) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                map[i][j] = Math.min(map[i][j], map[i][k] + map[k][j]);
            }
        }
    }