다익스트라 알고리즘

최단 경로

최단 경로 정의

• 간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중에 간선의 가중치의 합이 최소인 경로
• 가중치가 없으면 BFS로 짜서 도착지에 도착하면 중단시키게 짜주면 간단하다.
• 하지만, 가중치가 있으면 중간에 끝낼수가 없어 유리하지 않다.

하나의 시작 정점에 끝 정점까지의 최단 경로

• 다익스트라 알고리즘
  • 음의 가중치를 허용하지 않음
• 벨만포드 알고리즘
  • 음의 가중치 허용
• 모든 정점들에 대한 최단 경로
  • 플로이드 워샬 알고리즘

Dijkstra 알고리즘

• 시작 정점에서의 거리가 최소인 정점을 선택해 나가면서 최단 경로를 구하는 방식이다.
• 탐욕기법을 사용한 알고리즘으로 MST의 프림 알고리즘과 유사하다.
• 최소 신장트리랑 헷갈리면 안된다.

s: 시작 정점 , A: 인접 행렬, D : 시작 정점에서의 거리
v: 정점 집합, U: 선택된 정점 집합
Dijkstra(s, A, D)
	U = {s};

	FOR 모든 정점 V
		D[v] <- A[s][v]
	WHILE U!=V
		D[w]가 최소인 정점 w ∈ V-U를 선택
		U <- U U {w}
		FOR w에 인접한 모든 미방문 정점 v
			D[v] <- min(D[v], D[w] + A[w][v])

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

public class DijkstraTest {

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine().trim());
		int V = Integer.parseInt(st.nextToken()); //정점 갯수
		int start = 0;
		int end =  V-1; //도착점 인덱스
		final int INFINITY = Integer.MAX_VALUE;

		int[][] matrix = new int[V][V];
		int[] distance = new int[V];
		boolean[] visited = new boolean[V];

		for(int i=0; i<V; ++i){
			st = new StringTokenizer(in.readLine().trim(), " ");
			for(int j=0; j<V; ++j){
				matrix[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		Arrays.fill(distance, INFINITY);
		distance[start] = 0;

		int min=0, current=0;
		for(int i=0; i<V; ++i){
			//a단계 : 방문하지 않은 정점들 중 최소가중치의 정점 선택
			min = INFINITY;
			for(int j=0; j<V; ++j){
				if(!visited[j] && distance[j] < min){
					min = distance[j];
					current = j;
				}
			}
			visited[current] = true; // 선택 정점 방문 처리
			if(current == end){ // 선택 정점이 도착정점이면 탈출.
				break;
			}

			//b단계: current정점을 경유지로 하여 갈수 있는 다른 방문하지 않은 정점들에 대한 처리
			for(int c=0; c<V; ++c){
				if(!visited[c] && matrix[current][c] != 0
						&&  distance[c] > min+matrix[current][c]){
					distance[c] = min+matrix[current][c];
				}
			}
		}
		System.out.println(distance[end]);

	}

}