[알고리즘] 다익스트라 알고리즘

다익스트라 알고리즘 (Dijkstra Algorithm)

간단하게 하나의 정점에서 다른 점들로 가는 최단 경로를 구하고 싶을 때 사용한다

즉, 최단 거리를 구할 때 사용한다!

 

 

시작점을 D로 잡고 나머지 점까지의 최단 거리를 구해보자

 

 

1. 먼저 D가 시작점이니까 D에서 D까지의 거리는 0이다. 그리고 나머지는 무한대로 초기화한다

A	B	C	D	E
INF	INF	INF	0	INF

 

 

2. 다음으로 D와 연결된 노드는 C니까 C까지의 거리를 추가한다

A	B	C	D	E
INF	INF	4 (+4)	0	INF

 

 

3. 이제 C에서 방문한 노드는 제외하고 C와 연결된 노드를 찾는다. C는 A와 E로 갈 수 있으니까 추가한다. 이 때 각 노드까지의 최단 거리를 구해야 하므로 C까지의 최단거리에 다른 노드까지의 거리를 추가한다

A	B	C	D	E
6 (+2)	INF	4	0	INF

A	B	C	D	E
6	INF	4	0	10 (+6)

 

 

---

이런 식으로 모든 노드를 방문할 때까지 반복하면 된다

 

---

이제 알고리즘을 보자

 

구현 방법으로는 일반 배열을 이용하거나 우선순위 큐를 이용할 수 있다

우선순위 큐를 이용할 경우 훨씬 빠르므로 추천한다!

 

 

1. 일반 배열을 이용한 다익스트라

package graph;

import java.util.Arrays;
import java.util.Scanner;

public class Dijkstra {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int V = sc.nextInt();
		int E = sc.nextInt();
		int[][] adj = new int[V][V];
		for (int i = 0; i < E; i++) {
			adj[sc.nextInt()][sc.nextInt()] = sc.nextInt();
		}
		int[] D = new int[V];
		Arrays.fill(D, Integer.MAX_VALUE);
		boolean[] check = new boolean[V];

		D[0] = 0;
		for (int i = 0; i < V - 1; i++) {
			int min = Integer.MAX_VALUE;
			int index = -1;
			for (int j = 0; j < V; j++) {
				// 아직 처리하지 않았으면서, 가장 짧은 거리라면
				if (!check[j] && min > D[j]) {
					index = j;
					min = D[j];
				}
			}

			for (int j = 0; j < V; j++) {
				// 아직 처리하지 않았으면서 경로가 존재하고, index까지의 거리 + index부터 j까지의 거리가 D[j]보다 작다면
				if (!check[j] && adj[index][j] != 0 && D[index] != Integer.MAX_VALUE
						&& D[index] + adj[index][j] < D[j]) {
					D[j] = D[index] + adj[index][j];
				}
			}
			check[index] = true;
		}
		System.out.println(Arrays.toString(D));
	}

}

 

 

2. 우선순위 큐를 이용한 다익스트라

package graph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Dijkstra_pq {
	
	static class Edge implements Comparable<Edge> {
		int v, weight;

		public Edge(int v, int weight) {
			this.v = v;
			this.weight = weight;
		}

		@Override
		public int compareTo(Edge o) {
			// TODO Auto-generated method stub
			return Integer.compare(this.weight, o.weight);
		}

		@Override
		public String toString() {
			return weight + "";
		}

	}



	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int V = sc.nextInt();
		int E = sc.nextInt();
		List<Edge>[] adj = new ArrayList[V];
		for (int i = 0; i < V; i++)
			adj[i] = new ArrayList<>();
		for (int i = 0; i < E; i++) {
			// 첫번째가 출발지, 두번째가 도착지, 세번째가 가중치ㅋ
			adj[sc.nextInt()].add(new Edge(sc.nextInt(), sc.nextInt()));
		}
		//
		// dijkstra
		PriorityQueue<Edge> pq = new PriorityQueue<>();
		boolean[] check = new boolean[V];
		Edge[] D = new Edge[V];
		// 0번에서 출발하는걸로.
		for (int i = 0; i < V; i++) {
			// 원하는 출발지
			if (i == 0) {
				D[i] = new Edge(i, 0);
			} else {
				D[i] = new Edge(i, Integer.MAX_VALUE);
			}
			pq.add(D[i]);
		}
		while (!pq.isEmpty()) {
			Edge edge = pq.poll();

			for (Edge next : adj[edge.v]) {
				// check되지 않았으면서, D[next.v]가 D[edge.v] + next.weight 보다 더 크다면 갱신
				if (!check[next.v] && D[next.v].weight > D[edge.v].weight + next.weight) {
					D[next.v].weight = D[edge.v].weight + next.weight;
					// decrease key
					pq.remove(D[next.v]);
					pq.add(D[next.v]);
				}
			}
			check[edge.v] = true;
		}
		System.out.println(Arrays.toString(D));
	}
}

 

 

 

 

 

 

---

참고)

https://gaybee.tistory.com/34

[알고리즘/자바] 다익스트라 알고리즘 (Dijkstra Algorithm)