다익스트라 알고리즘 Dijkstra's algorithm

다익스트라 알고리즘

시작점에서 도착점을 가는 최단경로를 찾는 알고리즘.

가중치 그래프 탐색에 사용됨.

 

시작점 s에서 각 정점별 최단경로 구하기

슈도코드

DIJKSTRA(그래프, 가중치, 시작점)

     시작점 초기화

     최단경로의 비용을 MAX으로 초기화

     Queue <- Graph의 모든 정점을 추가함.             

     While ( Queue가 빌 때까지) {

            U <- Queue값에 들어있는 것 중 가장 작은 값을 추출.

            for ( V : U의 이웃 정점을 탐색){

                if( U를 거쳐서 V로 가는 경우가 V로 바로 가는 경우보다 비용이 작으면){

                     V로 가는 최단 경로 비용을 U를 거쳐서 V로 가는 비용으로 업데이트 

                } 

            }

     }

 

 

시간복잡도

배열로 구현한 경우  : O(N²)

힙 구조로 구현한 경우  : O(NlogN + ElogN)

피보나치 힙으로 구현한 경우 : O(NlogN + E) 

*N : 정점의 갯수

*E : 간선의 갯수

 

구현 JAVA

package algorithm;

import java.util.*;

public class dijkstra {
	
	public static void main(String[] args) {
		//배열을 이용하여 그래프 구현 
		int[][] graph = { { 0, 2, 3, 1, 0 },
				  { 2, 0, 0, 0, 4 },
				  { 3, 0, 0, 6, 5 },
				  { 1, 0, 6, 0, 7 },
				  { 0, 4, 5, 7, 0 }};
		//최단경로 결과값을 저장할 배열
		int[] queue = { Integer.MAX_VALUE,
				Integer.MAX_VALUE,
				Integer.MAX_VALUE,
				Integer.MAX_VALUE,
				Integer.MAX_VALUE };

		//다익스트라 실행
		dijkstra f = new dijkstra();
		f.dijkstra(graph, queue);
		
		//최단경로 결과값 출력
		System.out.println(Arrays.toString(queue));
		
	}

	public void dijkstra(int[][] graph, int[] queue) {
		
		//방문 여부를 저장할 배열
		boolean[] isVisited = new boolean[5];
		//시작점의 최단경로값 초기화
		queue[0] = 0;
		
		for(int i = 0; i<graph.length; i++) {
			// 최단경로값에서 최소값을 검색
			int u = findMin(queue, isVisited);
			//방문여부 true로 변환
			isVisited[u] = true;
						
			for(int v = 0; v<graph.length; v++) {
				//방문한 적이 없고, 경로가 있으며,
				//u를 거쳐서 v로 가는 게, 바로 v로 가는 경우보다 비용이 적으면
				if(!isVisited[v] && graph[u][v] != 0 
						&& (queue[u]+graph[u][v] < queue[v])) {
					// j로 가는 최단 경로 비용을 업데이트
					queue[v] = queue[u]+graph[u][v];
				}
			}
		}
		
	}

	private int findMin(int[] queue, boolean[] isVisited) {
		int minIndex = -1;
		int min = Integer.MAX_VALUE;
		//지금까지 방문하지 않은 값 중 취소 경로값을 탐색
		for(int i = 0; i<queue.length; i++) {
			if(queue[i]<=min && !isVisited[i]) {
				min = queue[i];
				minIndex = i;
			}
		}
		return minIndex;
	};	
	
}

[0, 2, 3, 1, 6]

출처

• 컴퓨터 알고리즘 기초 16강 다익스트라 알고리즘, T아카데미
• Dijkstra's Algorithm, programiz.com