[알고리즘 정리] Dijkstra(다익스트라)

 

 

다룰 내용

• Dijkstra 알고리즘
• 벨만 포드 알고리즘

 

---

 

Dijkstra 알고리즘

시작 정점에서 거리가 최소인 정점을 선택해가면서 최단 경로를 구하는 알고리즘으로 탐욕 기법을 이용하는 Prim 알고리즘과 유사합니다. 그러나 다익스트라의 경우 근시안적인 관점 때문에 음의 가중치가 있다면 사용할 수 없습니다.

 

 

Dijkstra 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Dijkstra {

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

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

		@Override
		public int compareTo(Vertex o) {
			return Integer.compare(this.weight, o.weight);
		}
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int V = Integer.parseInt(br.readLine());
		int end = V - 1;
		int adj[][] = new int[V][V];
		int d[] = new int[V];

		for(int i = 0; i < V; i++) { 
			String input2[] = br.readLine().split(" ");
			for(int j = 0; j < V; j++) {
				adj[i][j] = Integer.parseInt(input2[j]);
			}
		}

		boolean visited[] = new boolean[V];

		Arrays.fill(d, Integer.MAX_VALUE);

		//시작점이 a정점이라면 d[a] = 0;
		d[0] = 0;

		int min = 0, cur = 0;
		for(int i = 0; i < V; i++) {
			
			min = Integer.MAX_VALUE;
			
			for(int j = 0; j < V; j++) {
				if(!visited[j] && d[j] < min) {
					min = d[j];
					cur = j;
				}
			}
			
			if(visited[cur]) continue;
			visited[cur] = true;
			if(cur == end) break;

			for(int j = 0; j < V; j++) {
				if(!visited[j] && adj[cur][j] != 0 && min + adj[cur][j] < d[j]) {
					d[j] = min + adj[cur][j];
				}
			}
		}
		System.out.println(d[end]);
	}
}

 

 

Dijkstra + PQ(Priority Queue)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;

public class Dijkstra_pq {

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

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

		@Override
		public int compareTo(Vertex o) {
			return Integer.compare(this.weight, o.weight);
		}
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int V = Integer.parseInt(br.readLine());
		int end = V - 1;
		int adj[][] = new int[V][V];
		int d[] = new int[V];

		for(int i = 0; i < V; i++) { 
			String input2[] = br.readLine().split(" ");
			for(int j = 0; j < V; j++) {
				adj[i][j] = Integer.parseInt(input2[j]);
			}
		}

		boolean visited[] = new boolean[V];

		Arrays.fill(d, Integer.MAX_VALUE);

		//시작점이 a정점이라면 d[a] = 0;
		d[0] = 0;
		
		PriorityQueue<Vertex> q = new PriorityQueue<Vertex>();
		q.offer(new Vertex(0, d[0]));
		
		while(!q.isEmpty()) {
			
			Vertex cur = q.poll();
			
			if(visited[cur.v]) continue;
			visited[cur.v] = true;
			if(cur.v == end) break;

			for(int i = 0; i < V; i++) {
				if(!visited[i] && adj[cur.v][i] != 0 && cur.weight + adj[cur.v][i] < d[i]) {
					d[i] = cur.weight + adj[cur.v][i];
					q.offer(new Vertex(i, d[i]));
				}
			}
		}
		System.out.println(d[end]);
	}
}

 

 

---

 

벨만 포드 알고리즘

음의 가중치를 포함하느 그래프에서 최단 경로를 구할 수 있습니다. 단, 가중치의 합이 음인 사이클은 허용하지 않습니다.