[알고리즘] 그래프 알고리즘 1. 다익스트라 알고리즘

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

• 하나의 정점에서 다른 모든 정점까지의 최단 거리를 구할 때 사용.
• 음수 가중치 있을 때는 사용불가능. (현실 세계에서 사용하기 적합)
• Greedy한 접근법을 보인다. (특정 상황에서 최적 판단)

알고리즘 개요

1. 코스트(출발 노드와 거리) 테이블을 초기화 한다. (INF로 초기화)
2. 출발 노드 번호와 코스트(0)을 우선순위 큐에 넣고 코스트 테이블을 0으로 바꿔준다.
3. 큐에서 노드 하나를 꺼낸다
   3-1. 꺼낸 노드 코스트가 코스트 테이블의 값보다 크면 넘김 (넣었을 때는 최소였지만 뺄때는 아닐수도..?)
   3-2. 해당 노드와 인접한 노드들 중 (현재 노드 코스트 + 인접 노드와 거리) 가 해당 인접 노드의 코스트 테이블 값보다 작을 경우 테이블을 업데이트하고 큐에 넣음.
4. 3번 과정을 큐에 값이 없을 때까지 반복함.

소스 코드

public void Dijkstra() {
	dist[S] = 0;           
    pq.add(new Point(s, 0));
    while(!pq.isEmpty()) {
    	Point cur = pq.poll();
        if (dist[cur.node] < cur.cost) continue;
        for (int i = 0; i < edge.get(cur.node).size(); i++) {
        	int nextDist = cur.cost + edge.get(cur.node).get(i).cost;
            int nextNode = edge.get(cur.node).get(i).node;
            if (nextDist < dist[nextNode]) {
            	dist[nextNode] = nextDist;
                pq.add(new Point(nextNode, nextDist));
            }
        }
    }
}