[ 그래프 최단경로 ] 다익스트라

최단 경로 구하기

하나의 시작 정점에서 끝 정점가지의 최단 경로를 구한다.

다익스트라 알고리즘은 음의 가중치를 허용하지 않는다.

탐욕 기법을 사용한 알고리즘. MST(Minimum spanning tree)의 프림 알고리즘과 유사.

 

동작 과정 

1. 출발 노드를 설정.

2. 출발 노드를 기준으로 각 노드의 최소 비용을 저장.

3. 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택.

4. 해당 노드를 거쳐서 특정한 노드로 가는 경우를 고려하여 최소 비용을 갱신한다.

5. 위 과정에서 3~4번을 반복한다. 

다익스트라 - 우선순위 큐 

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

public class 다익스트라_PQ {
	static class Node implements Comparable<Node> {
		int v, w;

		public Node(int v, int w) {
			this.v = v;
			this.w = w;
		}

		@Override
		public int compareTo(Node o) {
			return Integer.compare(this.w, o.w);
		}

		@Override
		public String toString() {
			return "Node [v=" + v + ", w=" + w + "]";
		}
	}

	static final int INF = Integer.MAX_VALUE;
	static int V, E;
	static List<Node>[] adjList; // 인접리스트
	static int[] dist;

	public static void main(String[] args) {
		Scanner sc = new Scanner(input);

		V = sc.nextInt();
		E = sc.nextInt();

		adjList = new ArrayList[V];
		for (int i = 0; i < V; i++) {
			adjList[i] = new ArrayList<>();
		}

		dist = new int[V];
		Arrays.fill(dist, INF);
        
		for(int i = 0 ; i<E; i++) {
			int A = sc.nextInt();
			int B = sc.nextInt();
			int W = sc.nextInt();
			//유향 그래프
			adjList[A].add(new Node(B, W)); //인접리스트 삽입
		}//입력 끝
		
		dijkstra(0);
		System.out.println(Arrays.toString(dist));
	}

	private static void dijkstra(int start) {
		PriorityQueue<Node> pq = new PriorityQueue<>();
		
		boolean[] visited = new boolean[V]; //방문처리
		
		pq.add(new Node(start, 0));
		dist[start] = 0;			//시작 노드까지 거리는 0
		
		while(!pq.isEmpty()) {
			Node curr = pq.poll();
			
			if(visited[curr.v])continue;
			visited[curr.v]= true;
			
			//갱신 하는 작업
			for(Node n : adjList[curr.v]) {
				if(!visited[n.v] && dist[n.v] > dist[curr.v] + n.w) {
					dist[n.v]= dist[curr.v]+ n.w;
					pq.add(new Node(n.v, dist[n.v]));
				}
			}
			System.out.println(pq);
		}
	}

	static String input = "6 11\r\n" + "0 1 4\r\n" + "0 2 2\r\n" + "0 5 25\r\n" + "1 3 8\r\n" + "1 4 7\r\n"
			+ "2 1 1\r\n" + "2 4 4\r\n" + "3 0 3\r\n" + "3 5 6\r\n" + "4 3 5\r\n" + "4 5 12\r\n" + "";
}

 

다익스트라 - 반복문 

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

public class 다익스트라_반복문 {
	static class Node {
		int v, w;

		public Node(int v, int w) {
			this.v = v;
			this.w = w;
		}
	}

	static final int INF = Integer.MAX_VALUE;
	static int V, E; // V :정점의 수 , E : 간선의수
	static List<Node>[] adjList; // 인접리스트
	static int[] dist; // 최단 길이를 저장할 배열

	public static void main(String[] args) {
		Scanner sc = new Scanner(input);

		V = sc.nextInt();
		E = sc.nextInt();

		adjList = new ArrayList[V]; 
		for (int i = 0; i < V; i++) {
			adjList[i] = new ArrayList<>();
		}
        
		dist = new int[V]; // 거리값을 저장할 배열 
		Arrays.fill(dist, INF); // 초기값은 무한대로 채운다. 

		for (int i = 0; i < E; i++) {
			int A = sc.nextInt(); // 시작정점
			int B = sc.nextInt(); // 도착정점
			int W = sc.nextInt(); // 가중치

			// 유향 그래프
			adjList[A].add(new Node(B, W)); // 인접리스트에 노드 추가
		} // 입력 끝

		dijkstra(0);
		System.out.println(Arrays.toString(dist));
	}

	static void dijkstra(int start) {
		boolean[] visited = new boolean[V];
		
		dist[start] = 0;//시작 정점까지의 거리는 0으로 초기화
		
		for(int i = 0 ; i<V-1; i++) { // V-1, V 둘다 괜찮다. 
			int min = INF;
			int idx = -1;
			
			//선택하지 않은 정점 중 dist가 가장 작은 값을 골라 
			for(int j = 0 ; j<V; j++) {
				if(!visited[j] && min > dist[j]) {
					min = dist[j];
					idx = j;
				}
			}
			if(idx == -1) break; // 선택할 정점이 없다.
			
			visited[idx] = true; //선택
			
			for(int j = 0; j<adjList[idx].size(); j++) {
				Node curr = adjList[idx].get(j);
				
				//방문하지 않았고, 연결 되어있으면서 (인접리스트라 확인하지 않아도 된다)
				//이미 가지고 있는 값보다 갱신할 여지가 있으면 갱신.
				if(!visited[curr.v] && dist[curr.v] > dist[idx]+curr.w) {
					dist[curr.v] = dist[idx] + curr.w;
				}
			}
		}
	}
	static String input = "6 11\r\n" + "0 1 4\r\n" + "0 2 2\r\n" + "0 5 25\r\n" + "1 3 8\r\n" + "1 4 7\r\n"
			+ "2 1 1\r\n" + "2 4 4\r\n" + "3 0 3\r\n" + "3 5 6\r\n" + "4 3 5\r\n" + "4 5 12\r\n" + "";

}