Dijkstra 알고리즘

 다익스트라 알고리즘 또한 최단 경로를 구하는 알고리즘이다.

 

다익스트라는 최단 경로를 간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중에

 

간선의 가중치의 합이 최소인 경로로 정의했다.

 

즉, 크루스칼이나 프림은 모든 정점을 잇는 간선들의 최소 비용을 도출했다면,

 

다익스트라 알고리즘은 특정한 시작 정점과 특정한 끝 정점까지의 최단 경로를 도출할 수 있는 것이다.

 

다익스트라와 비슷하게 하나의 시작 정점에서 끝 정점까지의 최단 경로를 구하는 알고리즘이 또 하나 있다.

 

바로 벨만-포드(Bellman-Ford) 알고리즘이다.

 

벨만 포드알고리즘은 음의 가중치를 허용하지 않는 다익스트라 알고리즘과 반대로,

 

음의 가중치를 허용한 상태에서 시작 정점과 끝 정점까지의 최단 경로를 계산한다.

 

이런 특성의 차이를 염두에 두고 어떤 알고리즘을 쓸지 설계해야한다.

 

 

또, 모든 정점들에 대한 최단 경로를 도출하는 알고리즘이 있는데,

 

플로이드-워셜(Floyd-Warshall) 알고리즘이 바로 그것이다.

 

경유지, 출발지, 도착지 등으로 나눠서 계산하는데 추후 공부할 예정이다.

 

 

 다시 주제로 돌아가서, 다익스트라 알고리즘에 대해 더 자세히 알아보자.

 

다익스트라 알고리즘은 위에서 언급했듯이 시작 정점에서 끝 정점까지 최단 경로를 도출하는 알고리즘이다.

 

그렇다면 어떻게 도출할까?

 

간단하게 말하면 시작 정점에서 거리가 최소인 정점을 선택해 나가면서 최단 경로를 구하는 것이다.

 

해당 정점까지의 거리를 탐욕적으로 구하는 것이기 때문에 프림 알고리즘과 유사하다.

 

시작 정점과 끝 정점 사이에는 최단 경로를 가지는 정점이 존재하고,

 

이때 최단 경로는 시작 지점에서 경유지까지의 최단 경로와

 

경유지에서 끝 정점까지의 최단 경로로 구성된다.

 

 

 

 그렇다면 어떻게 동작할까?

 

우선 시작 정점을 입력 받고, 

 

거리를 저장하는 dist 배열을 엄청 큰 값으로 초기화 한 후, 시작 정점에서 갈 수 있는 곳의 값을 바꾼다.

 

아직 방문하지 않은 점들이 가지고 있는 거리 값과 현재 정점에서 방문하지 않은 정점까지의

 

가중치의 합이 작다면 변경한다.

 

이를 모든 정점을 방문할 때까지 반복한다.

 

이를 코드로 확인하면 다음과 같다.

 

static class Node{//그래프를 저장할 클래스
	int v,w;
    public Node(int v,int w){
    	this.v=v;
        this.w=w;
    }
}

static final int INF = Integer.MAX_VALUE;
static int V,E;// 정점, 간선의개수
static int List<Node>[] list;//유향그래프 저장 리스트
static int [] dist;// 최단 길이 저장 배열

 

 

우선 유향 그래프를 리스트에 저장하기 위해 Node 클래스를 만든다.

 

저장할 것은 목표 정점과 가중치.

 

다음으로는 dist를 초기화할 엄청 큰 값 INF와 정점과 간선의 개수를 입력받을 변수.

 

유향 그래프를 저장할 리스트와 각 정점에 따른 최단 길이를 저장할 배열도 선언한다.

 

dist = new int [V];
Arrays.fill(dist,INF);

for(int i=0;i<E;i++){
	int A= sc.nextInt();
    int B= sc.nextInt();
    int W= sc.nextInt();
    
    list[A].add(new Node(B,W));//유향 그래프이기 때문에 이렇게 저장.
}

dijkstra(0);//0번째 정점부터 시작


static void dijkstra(int st){
	boolean[] visited = new boolean[V];
    
    dist[st]=0;//시작 노드까지의 거리 0 설정
    
    for(int i=0;i<V-1;i++){
    	int min =INF;
        int idx=-1;
        
        for(int j=0;j<V;j++){//선택하지 않은 정점 중 dist가 짧은 것을 골라서 
        	if(!visited[j]&&min>dist[j]){
            	min=dist[j];
                idx=j;
            }
       	}
        if(idx==-1)break;// 선택할 정점이 없을 때 탈출
        
        v[idx]=true; //선택
        
        for(int j=0;j<list[idx].size();j++){
        	Node Cur=list[idx].get(j);
            
            if(!visited[cur.v]&&dist[cur.v]>dist[idx]+cur.w)
            	dist[cur.v]=dist[idx]+cur.w;
                //현재 저장되어 있는 거리보다 거쳐온 거리와 현재 가중치의 합이 더 작으면 
                //갱신
         }
 }

 

프림 알고리즘과 거의 차이가 없이 만들 수 있지만

 

마지막의 갱신할 때 비교하는 것이 살짝 다르다.

 

다익스트라는 거쳐온 거리와 해당 정점에서 목표 정점까지의 가중치의 합이

 

현재 저장되어있는 거리 값보다 작으면 갱신이 일어난다.

 

현재 A-D 사이의 거리가 저장되어 있고 이는 25라 가정했을 때,

 

비교할 거쳐온 거리는 A-B-C이고 이 값은 10, 현재 C에서 D까지의 가중치가 5라면 

 

비교할 값은 15.

 

즉, 현재 저장된 값은 25이고 비교할 값은 15이기 때문에 갱신이 일어난다.

 

또 이 때 저장된 값이 추후 

 

A부터 D까지의 최단 경로를 구하는데 바로 사용할 수 있다.

 

따라서 다익스트라 알고리즘을 구현하고 실행한 후 

 

A 정점부터 각 정점까지의 최단 경로가 가지는 가중치의 합을 바로 구할 수 있는 것이다.

 

라고 이해했다.