다익스트라

다익스트라

다익스트라 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘으로, 에지는 모두 양수 이어야 한다. 특정 노드에서 다른 노드들의 최단 거리를 구하는 문제가 주어졌을 때 다익스트라 알고리즘을 사용한다. 

 

시간 복잡도(노드 수 : V, 에지 수 : E)

O(ElogV)

 

다익스트라 알고리즘 핵심 이론

1. 인접 리스트로 그래프 구현하기

   다익스트라 알고리즘은 인접 행렬로 구현해도 좋지만 시간 복잡도 측면, N의 크기가 클 것을 대비해 인접 리스트를 선택하여 구현하는 것 이 좋다. 

2. 최단 거리 배열 초기화하기

   최단 거리 배열을 만들고, 출발 노드는 0, 이외의 노드는 무한으로 초기화한다. 이때 무한은 적당히 큰 값을 사용하면 된다.

3. 값이 가장 작은 노드 고르기

   최단 거리 배열에서 현재 값이 가장 작은 노드를 고른다. 여기서는 값이 0인 출발 노드에서 시작하면 된다.

4. 최단 거리 배열 업데이트하기

   선택된 노드에 연결된 에지의 값을 바탕으로 다른 노드의 값을 업데이트합니다. 1단계에서 저장해 놓은 연결 리스트를 이용해 현재 선택된 노드의 에지들을 탐색하고 업데이트하면 된다. 연결 노드 간 최단 거리는 두 값 중 더 작은 값으로 업데이트한다.

5. 과정 3 ~ 4를 반복해 최단 거리 배열 완성하기

   모든 노드가 처리될 때까지 3 ~ 4를 반복한다. 과정 4에서 선택 노드가 될 때마다 다시 선택되지 않도록 방문 배열을 만들어 처리하고, 모든 노드가 선택될 때까지 반복하면 최단 거리 배열이 완성된다.

 

최단 거리 업데이트 방법

Min(선택 노드의 최단 거리 배열의 값 + 에지 가중치, 연결 노드의 최단 거리 배열의 값)

 

다익스트라 알고리즘은 출발 노드와 그외 노드 간의 최단 거리를 구하는 알고리즘이고, 에지는 항상 양수여야 한다는 제약 조건이 있다.

많은 사람들이 다익스트라 알고리즘이 출발 노드와 도착 노드 간의 최단 거리를 구하는 알고리즘이라고 생각하는 경향이 있는데, 실제로 완성된 배열은 출발 노드와 이외의 모든 노드 간의 최단 거리를 표현한다.

 

코드로 표현

static int[] distance;
static boolean[] visit;
static ArrayList<Edge>[] list;
static PriorityQueue<Edge> q = new PriorityQueue<Edge>();

for(int i = 1; i <= S; i++) {
	list[i] = new ArrayList<Edge>();
}
for(int i = 0; i <= S; i++) {
	distance[i] = Integer.MAX_VALUE;
}
for(int i = 0; i < E; i++) {  // 가중치가 있는 인접 리스트 초기화하기
	list[u].add(new Edge(v, w));
}
q.add(new Edge(k, 0));   // k를 시작점으로 설정하기
distance[k] = 0;
while(!q.isEmpty()) {
	Edge current = q.poll();
    int c_v = current.vertex;
    if(visit[c_v]) {
    	continue;   // 이미 방문한 적이 있는 노드는 다시 큐에 넣지 않음
    }
    visit[c_v] = true;
    for(int i = 0; i < list[c_v].size(); i++) {
    	Edge tmp = list[c_v].get(i);
        int next = tmp.vertex;
        int value = tmp.value;
        if(distance[next] > distance[c_v] + value) { // 최소 거리로 업데이트하기
        	distance[next] = value + distance[c_v];
            q.add(new Edge(next, distacne[next]));
        }
    }
 }
class Edge implements Comparable<Edge> {
	int vertex, value;
    Edge(int vertex, int value) {
    	this.vertex = vertex;
        this.value = value;
    }
    public int compareTo(Edge e) {
    	if(this.value > e.value) {
        	return 1;
        }
        else {
        	return -1;
        }
  	}
}

위의 코드는 알고리즘과 관련된 코드만 표현한 코드입니다. 생략된 부분이 많으니 참고 바랍니다.