다익스트라 알고리즘(Dijkstra Algorithm)

다익스트라 알고리즘?

 -> 그래프 상에 존재하는 두 노드 간의 최단 거리를 구하고 싶을 때 이용하는 알고리즘.

 -> 사이클 포함 X

 -> 음의 가중치가 존재하면 사용 불가능.

 

 

 매커니즘

  1) 체크되어있지 않은 정점 중에서 D(Distance)의 값이 가장 적은 정점(또는 시작점)을 선택(우선순위 큐에 삽입)

  2) 우선순위 큐에서 해당 점을 꺼내고, 이 점을 인덱스로 하는 visited 배열의 값을 True로 변경(방문했다는 표시) -> 방문 따지면 안되는 경우도 있음..! 

  3) 해당 점과 연결된 모든 점을 검사(방문 여부에 관계 없이 진행. 그 이유는 최단 경로가 갱신될 수 있으므로)

  4) 해당 점을 x, 연결된 다른 끝 점을 y, 이동하는 Weight를 w라고 했을 때, D[y] > D[x] + w를 만족하면 D[y] 의 값을 갱신하고 우선순위 큐에 넣는다.

  5) 모든 점을 방문하기 전까지 반복.

다익스트라 매커니즘(출처 : 내 알고리즘 수업 피피티 자료)

 

수도코드

---

다익스트라 수도코드

 

수도코드만 보는 것보다 전체 샘플 코드를 보는 것이 더 이해가 쉬울 듯.

 

 

전체 샘플코드

---

private static void dijkstra(int v, int startPoint) {
		PriorityQueue<EndVertex> queue = new PriorityQueue<>();	// comparable로 객체 우선순위 바꿈
		distance[startPoint] = 0;
		queue.offer(new EndVertex(startPoint, distance[startPoint]));
		
		while(!queue.isEmpty()) { 
			EndVertex startVertex = queue.poll();
			startPoint = startVertex.getEndPoint();
			visited[startPoint] = true;
			// 시작 점 빼고 모든 vertex를 방문하기 전까지 경로 탐색
			for(EndVertex vertex : graph[startPoint]) {
				int endPoint = vertex.getEndPoint();
				if(!visited[endPoint] && distance[endPoint] > distance[startPoint] + vertex.getWeight()) {
					distance[endPoint] = distance[startPoint] + vertex.getWeight();
					queue.offer(new EndVertex(endPoint, distance[endPoint]));	
				}
			}
		}
	}