다익스트라(dijkstra)

다익스트라 알고리즘 정리

다익스트라란?

• 그래프에서 시작 노드 → 모든 노드까지 최단 거리를 탐색하는 알고리즘
• 특징: 모든 가중치는 양수여야 한다
• 시간복잡도
  • O(V^2)
  • 우선순위 큐 사용 시 → O(E log V)
  • (V = 노드 수, E = 간선 수)

1. 인접 리스트로 그래프 구현하기

인접 행렬보다 효율적 → (노드, 가중치) 형태로 리스트에 저장

 List<List<Edge>> adj = new ArrayList<>(N + 1); 
for (int i = 0; i <= N; i++) adj.add(new ArrayList<>()); 
for (int i = 0; i < M; i++) { 
	int u = fs.nextInt(), 
    v = fs.nextInt(), 
    w = fs.nextInt(); 
    adj.get(u).add(new Edge(v, w)); 
    // 무방향이면 adj.get(v).add(new Edge(u,w)); 
} 

2. 최단 거리 배열 초기화

 int[] dist = new int[N + 1]; Arrays.fill(dist, INF); dist[S] = 0; 

3. 값이 가장 작은 노드 고르기

 PriorityQueue<Long> pq = new PriorityQueue<>(Long::compare); pq.offer(((long)dist[S] << 32) | (S & 0xffffffffL)); 

4. 최단 거리 배열 업데이트

 while (!pq.isEmpty()) { long key = pq.poll(); int d = (int)(key >>> 32); // 상위 32비트: 거리 int u = (int) key; // 하위 32비트: 정점 번호
// 오래된 정보는 건너뜀
if (d != dist[u]) continue;

// u에서 나가는 모든 간선 확인
for (Edge e : adj.get(u)) {
    int v = e.to;
    int nd = d + e.w;   // u까지 거리 d + (u→v 가중치)

    if (nd < dist[v]) {
        dist[v] = nd;
        pq.offer(((long)nd << 32) | (v & 0xffffffffL));
    }
}


}

정리

1. 그래프를 인접 리스트로 만든다
2. 최단 거리 배열(dist) 초기화
3. PQ에서 가장 가까운 노드를 꺼낸다
4. 연결된 노드들의 거리 완화 → 갱신 시 PQ에 다시 넣기
5. 모든 노드가 선택될 때까지 반복