[개념]다익스트라 알고리즘

백준을 풀다가 다익스트라 알고리즘이 나왔다. 분명히 학부때 배운 내용인데 오랜만에 하려니 기억이 잘 나지 않아서 책을 뒤져 봤다. 

 

해당 알고리즘은 최단 경로를 구할 때 많이 사용한다. 가중치가 없는 그래프에서 최단 경로를 찾는 방법은 너비 우선 검색으로 구현하면 되지만, 가중치가 있는 경우에는 BFS만 가지고는 문제를 해결할 수 없다. 

 

모서리 또는 정점에 가중치가 부여된 그래프에서 두 정점 사이의 최단 경로를 찾을 때는 다익스트라 알고리즘을 이용하면 된다. 이 알고리즘에서는 어떤 시작점 S가 주어졌을 때, 그 정점에서 시작하여 다른 모든 정점으로 가는 최단 경로를 찾을 수 있기 때문에, 결과적으로 어떤 최종 목적지 t로 가는 최단 경로를 구할 수 있다.

 

기본적인 개념은 프림 알고리즘과 매우 비슷하다. 각 단계에서 s로부터의 최단 경로를 알고 있는 정점으로 구성된 트리에 새로운 정점을 한 개씩 추가한다. 프림 알고리즘에서와 마찬가지로 트리 밖에있는 정점하고 연결되는 모서리 가운데 가장 비용이 작은 모서리를 추적하면서 비용이 작은 정점부터 하나씩 추가한다. 

 

하지만 다익스트라 알고리즘과 프림 알고리즘은 트리에 추가할 정점을 선택하는 기준이 다르다. 최소 신장 트리 문제에서는 트리 모서리로 새로 추가할 수 있는 것들 가운데 가중치가 가장 작은 것을 추가한다. 하지만 최단 경로 문제에서는 시작점으로부터 가장 가까운정점부터 추가한다. 새로운 모서리의 가중치 외에도 트리 시작점으로부터 새로 추가할 모서리에 인접한 정점까지의 거리도 고려해야한다. 

 

dijkstra(graph g, int start){ 

	int i,j;					//카운터
    bool intree[MAXV];			//정점이 트리에 들어있는지 여부
    int distance[MAXV];			//시작점으로부터 거리
    int v;						//지금 처리할 정점
    int w;						//다음 정점 후보
    int weight;					//모서리의 가중치
    int dist;					//현재 최단 거리
    
    for(i=1; i<=g-nvertices; i++){
    	intree[i] = FALSE;
        distance[i] = MAXINT;
        parent[i] = -1;
    }
    distance[start] = 0;
    v = start;
    
    while(intree[v] == FALSE){
    	intree[v] = TRUE;
        for(i=0; i<g-degree[v]; i++){
        	w=g->edges[v][i].v;
            weight = g -> edges[v][i].weight;
            if(distance[w] > (distance[v]+weight)){
            	distance[w] = distance[v]+weight;
                parent[w] = v;
            }
        }
        v=1;
        dist = MAXINT;
        for(i=1; i<=g->nvertices; i++){
        	if((intree[i]==FALSE) && (dist > distance[i])){
            	dist = distance[i];
                v=i;
            }
        }
    }
    

}