최단 거리 : Shortest Path

최단 거리 : Shortest Path

: 그래프의 시작점에서 다른 지점까지의 최단 거리

이름	간선의 가중치	시작점	도착점	시간 복잡도
BFS	모두 1	한 정점	모든 정점	O (V+E)
✅ Dijkstra	≥ 0	한 정점	모든 정점	O (E log V)

→ Dijkstra가 BFS 보다 시간 복잡도가 좋다!

• 탐색(Search) : 시작점에서 간선을 0개 이상 사용해 갈 수 있는 정점들은 무엇인가?
  • DFS / BFS ( → 가중치가 적용되지 ❌ 때, 다른 정점까지 최소 이동 횟수도 계산 가능 )

---

Dijkstra Algorithm

• 요약
  • input
    • Graph G<V,E> = 가중치가 0이상인 가중치 그래프
    • 시작 정점이 주어짐
  • Output
    • 시작점에서 모든점까지의 최단 경로의 거리
  • Time Complexity
    • O (E log V)
• 필요한 정보
  • dist[i] : 시작점에서 i번 정점까지 가능한 최단 거리
  • 자료구조 D := { (v,d) | 시작점에서 v까지 d만에 갈 수 있음을 확인한다. }
• 순서도

  1️⃣ → 2️⃣ 🔁 6️⃣ →  if( D == null )→ clear

  1️⃣ dist 배열 초기화 if(i == S) dist[i] 이면 0 // 시작점에서 시작점까지 거리는 0 else dist[i] 이면 무한 // 시작점 제외 최단거리 측정한 적 없음 자료구조 D에 D(S,0) 추가 // 시작점에서 시작점까지 거리 0 2️⃣ D가 비었나 ? 3️⃣ 자료구조 D에서 가장 작은 d(거리)를 갖는 Info(v,d)를 뽑는다. 4️⃣ 위에서 뽑은 Info(v,d)의 가치 판단 dist[v] < d → v까지의 최단거리보다 d가 크다면 가치가 없는 정보이므로 폐기 (v,d) 5️⃣ (v,d)를 통해 새로운 정보를 D에 추가 d + c < dist[w] // 지금까지 알던 w보다 , d+c가 작다면 → dist[w] = d + c // dist[w] 업데이트 → (w , d+c) // 자료구조 D도 업데이트 6️⃣ 종료
  
• 시간 복잡도 = O(E log E) = O(E log V)
  • 5️⃣ (v,d)의 가치판단 ? 모든 정점이 최대 한번씩 , 가치가 있는 v로 등장한다.
    • int x = que.poll();하고 x와 연결된 간선들을 한번씩 본다. 그래서 N(5️⃣) = deg(1) + deg(2) +… deg(v) = |E| (간선의 개수) 이다.
      • 모든 정점의 차수의 합은 간선의 합과 같다.
    • T(전체 시간) ≤ [T(5️⃣) + T(3️⃣)] X E = O(E log E) T(3️⃣) = D에서 최소 d를 갖는 자료를 추출하는 시간 T(5️⃣) = D에 임의의 (v,d)라는 자료를 삽입하는 시간
      
• 음수 간선이 있으면 안되는 이유
  • 한 정점이 v로 추출되는 횟수가 한 번이 아니다.
  • N(5️⃣) >> |E| 이므로, 시간 복잡도가 보장되지 않고 오랜 시간 소요된다.
• 구현

  // 1️⃣ dist 배열 초기화, 자료구조 D에 D(S,0) 추가
  static void dijkstra(int start){
  	// TODO : dist 배열 초기화, (S,0)을 D에 저장
  	// 모든 정점까지에 대한 거리를 무한으로 초기화, 
  	// 문제의 정답으로 가능한 거리의 최댓값보다 큰 값임을 보장해야하므로 최대치 고려해서 Integer.MAX_VALUE
  	for(int i=1;i<=N;i++) dist[i] = Integer.MAX_VALUE;
  
  	// 최소 힙 생성
  	PriorityQueue<Info> pq = new PriorityQueue<>(Comparator.comparingInt(o -> o.dist));
  
  	// 시작점에 대한 정보를 기록에 추가하고, 거리 배열에 갱신
  	pq.add(new Info(start, 0);
  	dist[start] = 0;
  }
  // 2️⃣ queue가 비었나 ? 
  while(!pq.isEmpty()){
  	// 3️⃣ 최소의 (v,d) 추출
  	Info info = pq.poll(); 
  
  	// 4️⃣ 꺼낸 정보가 최신과 다르면, 의미 없이 낡은 정보이므로 폐기
  	if(dist[info.idx] < info.dist) continue;
  
  	// 5️⃣ (v,d)로 새로운 정보 D에 추가 
  	for(Edge e : edges[info.idx]){
  		if(dist[info.idx] + e.weight >= dist[e.to]) continue;
  	
  		dist[e.to] = dist[info.idx] + e.weight;
  		pq.add(new info(e.to,dist[e.to]));
  	}
  
  }
  

---

BOJ_1916

• 정답의 최대치 최단거리의 특성 같은 정점을 두번 방문 할 이유가 없다. 사이클이 있으면 좋은 최단 거리가 나오지 않는다. 따라서 정답은 최대 버스비(10만) * 정점수(1천) = 1억 이하 이므로 Integer면 충분
  
• 시간,공간 복잡도
  • O(E log V) = 10만 *log 1천 = 100만 → 1초 안에 가능
• 구현

  static void dijkstra(int start){
  	// 모든 정점까지에 대한 거리 무한으로 초기화
  	for(int i=1;i<=N;i++) dist[i] = Integer.MAX_VALUE;
  
  	// 최소 힙 생성
  	PrioityQueue<Info> pq = new PriorityQueue<>(Comparator.comparingInt(o -> 
  	
  // 시작점에 대한 정보를 기록에 추가, 거리배열에 갱신
  	pq.add(new info(start,0);
  	dist[start] = 0;
  
  	// 거리 정보들이 모두 소진될 때까지 거리 갱신 반복
  	while(!pq.isEmpty()){
  		Info info = pq.poll();
  
  		if(dist[info.idx] < info.dist) continue;
  	
  		for(Edge e : edges[info.idx]){
  			if(dist[info.idx] + e.weight >= dist[e.to]) continue; // 새롭게 찾은 거리 e.to
  			dist[info.idx] = dist[info.idx] + e.weight;
  		}
  	}