TIL:다익스트라 알고리즘

Dijkstra Algorithm

• 한 노드에서 다른 모든 노드에 대한 최단 거리를 구하는 알고리즘
• 방향, 무방향 그래프에서 사용 가능
• 음의 가중치가 있는 경우 사용 불가능
• 시간 복잡도 : O(V²)
  • 우선순위 큐(=힙 트리 사용) : O(E log V)

알고리즘

1. 최단 거리를 저장할 배열 d[v]를 생성 후 시작 노드는 0, 이외의 노드는 INF 값으로 초기화
2. 현재 노드 a의 시작 노드를 저장
3. a로 부터 갈 수 있는 임의의 노드 b에 대해 d[b]와 d[a] + p[a][b]의 값을 비교
4. d[b] > d[a] + p[a][b] => d[b] = d[a] + p[a][b]
5. 모든 이웃 노드에 대해 해당 작업을 처리
6. a를 방문 상태로 처리
7. 미방문 상태의 노드 중 출발 노드로부터 가장 짧은 노드를 찾아 a에 저장
8. 도착노드가 방문 상태이거나 더 이상 방문할 수 있는 노드가 없을 때 종료
9. 3 ~ 7 반복

코드

for(int i = 0; i < v; i++)
	d[v] = INF;
    
d[start] = 0;
q.add(new Node(start, d[start]));

while(!q.isEmpty()){
	Node cur = q.poll();
    
    size = adj[cur.pos].size();
    for(int i = 0; i < size; i++){
    	int next = adj[cur.pos].get(i).pos;
        int cost = adj[cur.pos].get(i).cost + d[cur.pos];
        
        if(d[next] > d[cur.pos] + cost){
        	d[next] = d[cur.pos] + cost;
            q.add(new Node(next, cost));
        }
    }
}