[알고리즘] 최단 경로 - 다익스트라, 벨만포드, 플로이드워샬 알고리즘

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

 

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

• 다익스트라(dijkstra) 알고리즘 : 음의 가중치 허용X, 그리디 알고리즘의 일종.
• 벨만-포드(Bellman-Ford) 알고리즘 : 음의 가중치 허용.

- 모든 정점들에 대한 최단 경로

• 플로이드-워샬(Floyd-Warshall) 알고리즘

---

< Dijkstra 알고리즘 >

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

---

s: 시작 정점, A: 인접행렬, D: 시작정점에서 자신 정점까지의 최단 거리

V: 정점 집합, U: 선택된 정점 집합

 

Dijkstra(s, A, D)                                             

    U = {s};                                                   

   For 모든 정점 v                                          

        D[v] ← A[s][v]    // s에서 v로 가는 직접 비용

                                                                 

  While U ≠ V                                               

        D[w]가 최소인 정점 w∈ V-U 선택              

        U ← U ∪ {w}                                        

        For w에 인접한 모든 미방문 정점 v            

            D[v] ← min(D[v], D[w] + A[w][v])           

 

---

다익스트라 자바 구현 코드

: priority queue 를 사용하면 가중치 비교 시간을 줄일 수 있다.

public class DijkstraTest2_PQ {
	
	static class Vertex implements Comparable<Vertex> {
		int no, totalDistance;
		
		public Vertex(int no, int totalDistance) {
			super();
			this.no = no;
			this.totalDistance = totalDistance;
		}
		
		@Override
		public int compareTo(Vertex o) {
			return this.totalDistance - o.totalDistance;
		}
	}
	
	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int V = Integer.parseInt(in.readLine());
		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++) {
			StringTokenizer st = new StringTokenizer(in.readLine(), " ");
			for (int j = 0; j < V; j++) {
				matrix[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		PriorityQueue<Vertex> pQueue = new PriorityQueue<>();
		
		Arrays.fill(distance, INFINITY);	// 처음엔 아무데도 못가게
		distance[start] = 0;	// 자신에서 자신으로 가는 비용은 0
		pQueue.offer(new Vertex(start, distance[start]));
		
		Vertex current = null;
		
		while(!pQueue.isEmpty()) {
			current = pQueue.poll();	// distance 최소인 vertex가 나옴
			if(visited[current.no]) continue;	//PQ에 남아있던 totalDistance의 최소비용보다 더 큰 상태
			
			visited[current.no] = true;
			if(current.no == end) break;	// 출발지로부터 모든 노드의 최단거리 구하려면 이거 지우기
			
			// 2단계: 선택된 current 정점을 경유지로 해서 아직 방문하지 않은 다른 정점으로의 최단경로 비용 계산하여 유리하면 update
			for (int j = 0; j < V; j++) {
				// 방문하지 않았고, 내 자신으로 가는 노드 아니고, distance가 경유지를 방문하여 지나가는게 더 최소이면 update 
				if(!visited[j] && matrix[current.no][j] != 0 && distance[j] > current.totalDistance + matrix[current.no][j]) {
					distance[j] = current.totalDistance + matrix[current.no][j];
					pQueue.offer(new Vertex(j, distance[j]));
				}
			}
			
		}
		
		System.out.println(distance[end]);	// 도착지까지 최단 구할 때
		
	}	// end of main
	
	
}