다익스트라

최단경로

• 간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중에 간선의 가중치의 합이 최소인 경로

다익스트라(dijkstra)

• 음의 가중치가 없을때 사용 가능
• 시작 정점에서 다른 모든 정점으로의 최단 경로를 구하는 알고리즘
• 시작 정점에서의 거리가 최소인 정점을 선택해 나가면서 최단 경로를 구하는 방식
• 탐욕 기법을 사용한 알고리즘으로 MST 프림과 유사

구현

• 준비

package algo_0903;

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

public class DijkstraTest {
	
	static class Node{
		int v, w;
		Node next;
		public Node(int v, int w, Node next) {
			super();
			this.v = v;
			this.w = w;
			this.next = next;
		}

	}
	
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int V = Integer.parseInt(st.nextToken());
		int E = Integer.parseInt(st.nextToken());
		
		st = new StringTokenizer(br.readLine());
		int start = Integer.parseInt(st.nextToken());
		int end = Integer.parseInt(st.nextToken());
		
		Node[] adjList = new Node[V];
		for(int i = 0 ; i < E; i++) {
			st = new StringTokenizer(br.readLine());
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());
			int weight = Integer.parseInt(st.nextToken());
			adjList[from] = new Node(to, weight, adjList[from]);
		}
		
		System.out.println(getMinDistance(adjList, start, end));

	}
	
	
	static int getMinDistance(Node[] adjList, int start, int end) {
		final int V = adjList.length;
		int[] minDistance = new int[V]; // 시작 정점에서 자신으로의 최소거리
		boolean[] visited = new boolean[V]; // 방문한 정점 관리
		final int INF = Integer.MAX_VALUE;
		Arrays.fill(minDistance, INF);
		minDistance[start] = 0;
		
		for(int i = 0 ; i < V; i++) {
			// step 1 : 미방문 정점 중 시작정점에서 가장 가까운 정점(stopOver) 선택
			int min = INF;
			int stopOver = -1;
			for(int j = 0 ; j < V; j++) {
				if(!visited[j] && min > minDistance[j]) {
					min = minDistance[j];
					stopOver = j;
				}
			}
//			if(stopOver == end) break; //도착지까지만 구하기
			if(stopOver == -1) break;
			visited[stopOver] = true;
			
			// step 2 : 선택된 정점(stopOver)을 경유해서 미방문 인접한 정점으로의 최소비용을 갱신할 수 있는지 체크
			for(Node temp = adjList[stopOver]; temp != null; temp = temp.next) {
				if(!visited[temp.v] && minDistance[temp.v]>min+temp.w) {
					minDistance[temp.v] = min + temp.w;
				}
			}
		}
		
		return minDistance[end] != INF ? minDistance[end] : -1;
	}
}