Dijkstra&#s 알고리즘 이해: 이론에서 구현까지

Dijkstra의 알고리즘은 그래프 이론에서 그래프의 소스 ​​노드에서 다른 모든 노드까지의 최단 경로를 찾는 데 사용되는 고전적인 경로 찾기 알고리즘입니다. 이 기사에서는 알고리즘과 정확성 증명을 살펴보고 JavaScript로 구현하는 방법을 제공합니다.

Dijkstra의 알고리즘이란 무엇입니까?

Dijkstra의 알고리즘은 음이 아닌 간선 가중치를 갖는 가중치 그래프에서 단일 소스 노드로부터 최단 경로를 찾도록 설계된 탐욕스러운 알고리즘입니다. 1956년 Edsger W. Dijkstra가 제안한 이 알고리즘은 컴퓨터 과학에서 가장 널리 사용되는 알고리즘 중 하나로 남아 있습니다.

입력 및 출력

• 입력: 그래프 $지=(뷔,E)$G=(V,E) , 어디 $뷔$뷔 는 정점의 집합이고, $E$E 는 에지 세트이고 소스 노드입니다. $s\in Vs$s∈뷔
• . 출력: 최단 경로 거리 $님의$님 다른 모든 노드에 $뷔$뷔

.

핵심 개념
휴식:
2. 알려진 노드까지의 최단 거리를 업데이트하는 프로세스입니다.
우선순위 큐:
3. 임시 거리가 가장 짧은 노드를 효율적으로 가져옵니다.
그리디 접근 방식:

최단 거리가 감소하지 않는 순서로 노드를 처리합니다.

알고리즘

1. 
   

   거리 초기화:
   $$\text{거리}()=0,\text{거리}(v)=\mathrm{무한}\mathrm{\forall }v\mathrm{\ne }s$$거리(s)=0,거리(v)=∀v=s

2. 우선순위 대기열을 사용하여 거리에 따라 노드를 저장합니다.

3. 거리가 가장 짧은 노드를 반복적으로 추출하고 이웃 노드를 이완시킵니다.

휴식 - 수학적 설명

• 초기화: $\text{거리}(s)=0,\text{거리}(v)=\mathrm{}\text{모두}v\mathrm{\ne }s$거리(s)=0,거리(v)= llv=

어디 $(s)$(들) 소스 노드이고, $(v)$(v) 다른 노드를 나타냅니다.

• 이완 단계: 각 가장자리에 대해 $(u,v)$(u,v) 무게로 $w(u,v)$w(u,v) : 만약에 $\text{거리}(v)>\text{거리}(유)w(u,v)$dist(v)>dist (유) w(u,v) , 업데이트:
  $$\text{거리}(v)=\text{거리}(유)w(u,v),\text{이전}(v)=u$$거리(v)=거리(u) w(u,v),prev(v)=u

작동 이유: 완화는 더 짧은 경로가 발견되면 거리를 점진적으로 업데이트하여 항상 노드까지의 최단 경로를 찾도록 보장합니다.

---

우선순위 대기열 - 수학적 설명

• 큐 작업:

  • 우선순위 대기열은 항상 노드를 대기열에서 제거합니다. $(u)$(유) 임시 거리가 가장 작은 경우:
    $$유=\mathrm{a\; rg}\underset{v\in Q}{분}\text{거리}(v)$$u=arg v∈Q 분​거리(v)
  • 작동 이유: 가장 작은 노드를 처리하여 $(\text{거리}(v))$(dist(v)) , 우리는 소스에서 소스까지의 최단 경로를 보장합니다. $(u)$(유) .

---

정확성 증명

강한 유도를 이용하여 Dijkstra 알고리즘의 정확성을 증명합니다.

강인덕션이란 무엇인가요?

강귀납법은 수학적 귀납법의 변형으로, 명제를 증명하기 위해 $(피(n))$(P(n)) , 우리는 $(피(1),피(2),\dots ,피(k))$(P(1),P(2),…,P(k)) 증명하다 $(피(k1))$( P(k 1)) . 이는 일반 유도와는 다릅니다. $(피(k))$(P(k)) 증명하다 $(피(k1))$( P(k 1)) . 다른 게시물에서 더 자세히 살펴보세요.

다익스트라 알고리즘의 정확성(귀납적 증명)

1. 기본 사례:
   
   소스 노드 $(s)$(들) 로 초기화됩니다 $\text{거리}(s)=0$거리(s)=0 , 맞습니다.

2. 귀납적 가설:
   
   지금까지 처리된 모든 노드의 최단 경로 거리가 정확하다고 가정합니다.

3. 유도 단계:
   
   다음 노드 $(u)$(유) 우선순위 큐에서 제외됩니다. 부터 $\text{dist}(u)$거리(u) 는 남은 최소 거리이며 모든 이전 노드의 거리가 정확합니다. $\text{dist}(u)$거리(u) 도 맞습니다.

---

자바스크립트 구현

전제 조건(우선순위 대기열):

// Simplified Queue using Sorting
// Use Binary Heap (good)
// or  Binomial Heap (better) or Pairing Heap (best) 
class PriorityQueue {
  constructor() {
    this.queue = [];
  }

  enqueue(node, priority) {
    this.queue.push({ node, priority });
    this.queue.sort((a, b) => a.priority - b.priority);
  }

  dequeue() {
    return this.queue.shift();
  }

  isEmpty() {
    return this.queue.length === 0;
  }
}

다음은 우선순위 대기열을 사용하는 Dijkstra 알고리즘의 JavaScript 구현입니다.

function dijkstra(graph, start) {
  const distances = {}; // hold the shortest distance from the start node to all other nodes
  const previous = {}; // Stores the previous node for each node in the shortest path (used to reconstruct the path later).
  const pq = new PriorityQueue(); // Used to efficiently retrieve the node with the smallest tentative distance.

  // Initialize distances and previous
  for (let node in graph) {
    distances[node] = Infinity; // Start with infinite distances
    previous[node] = null; // No previous nodes at the start
  }
  distances[start] = 0; // Distance to the start node is 0

  pq.enqueue(start, 0);

  while (!pq.isEmpty()) {
    const { node } = pq.dequeue(); // Get the node with the smallest tentative distance

    for (let neighbor in graph[node]) {
      const distance = graph[node][neighbor]; // The edge weight
      const newDist = distances[node] + distance;

      // Relaxation Step
      if (newDist < distances[neighbor]) {
        distances[neighbor] = newDist; // Update the shortest distance to the neighbor
        previous[neighbor] = node; // Update the previous node
        pq.enqueue(neighbor, newDist); // Enqueue the neighbor with the updated distance
      }
    }
  }

  return { distances, previous };
}

// Example usage
const graph = {
  A: { B: 1, C: 4 },
  B: { A: 1, C: 2, D: 5 },
  C: { A: 4, B: 2, D: 1 },
  D: { B: 5, C: 1 }
};

const result = dijkstra(graph, 'A'); // start node 'A'
console.log(result);

경로 재구성

// Simplified Queue using Sorting
// Use Binary Heap (good)
// or  Binomial Heap (better) or Pairing Heap (best) 
class PriorityQueue {
  constructor() {
    this.queue = [];
  }

  enqueue(node, priority) {
    this.queue.push({ node, priority });
    this.queue.sort((a, b) => a.priority - b.priority);
  }

  dequeue() {
    return this.queue.shift();
  }

  isEmpty() {
    return this.queue.length === 0;
  }
}

예제 연습

그래프 표현

• 노드: $A,B,C,D$A,B,C,D
• 가장자리:
  • $A\to B=(1),A\to C=(4)$A→B=(1),A→C=(4)
  • $B\to C=(2),B\to D=(5)$B→C=(2),B→D=(5)
  • $ㄷ\to ㄷ=(1)$C→D=(1)

단계별 실행

1. 거리 초기화:
   

   $$\text{거리}(A)=0,\text{거리}(B)=\mathrm{},\text{거리}(C)=\mathrm{🎉},\text{거리}(D)=\mathrm{}$$거리(A)=0,거리(B)= ,거리(C)=,거리(D)=무한대

2. 프로세스 A:

   • 가장자리 완화: $A\to B,A\to C\mathrm{.}$거리(B
     )=$$\text{,}\hspace{0.25em} \mathrm{거리}(C\mathrm{)}=\text{4}\text{텍스트{거리}(B) = 1, ; 텍스트{거리}(C) = 4}거리(B)=1,\mathrm{거리}(C)=$$ 프로세스 B: 가장자리 완화:
   B
3. →
   C
   • ,B$D.BB\to C,B\to D.\mathrm{}$거리(ㄷ
     )=$$\text{,}\hspace{0.25em} \mathrm{거리}(D\mathrm{)}=\text{6}\text{텍스트{거리}(C) = 3, ; 텍스트{거리}(D) = 6}거리(C)=3,\mathrm{거리}(D)=$$ 프로세스 C: 편안한 가장자리:
   C
4. →
   D
   • .C~D. $C\to D.\mathrm{}$거리(디
     )=$$\text{텍스트{dist}(D) = 4}거리(D)=4\mathrm{}$$

   • 프로세스 D:

     • 추가 업데이트는 없습니다.

   최종 거리 및 경로

   $$\text{거리}(A)=0,\text{거리}(B)=1,\text{거리}(C)=3,\text{거리}(D)=4$$거리(A)=0,거리(B)= 1,거리(C)=3,거리(D)=4
   
   
   $$A\to B\to ㄷ\to D$$A→B→C→D

   최적화 및 시간 복잡도

   다양한 우선순위 대기열 구현을 통한 Dijkstra 알고리즘의 시간 복잡도 비교:

   Priority Queue Type	Insert (M)	Extract Min	Decrease Key	Overall Time Complexity
   Simple Array	O(1)	O(V)	O(V)	O(V^2)
   Binary Heap	O(log V)	O(log V)	O(log V)	O((V E) log V)
   Binomial Heap	O(log V)	O(log V)	O(log V)	O((V E) log V)
   Fibonacci Heap	O(1)	O(log V)	O(1)	O(V log V E)
   Pairing Heap	O(1)	O(log V)	O(log V)	O(V log V E) (practical)

   핵심 포인트:

   1. 간단한 배열:
      • extract-min에 대한 선형 검색으로 인해 큰 그래프에는 비효율적입니다.
   2. 바이너리 힙:
      • 단순성과 효율성의 균형으로 인해 표준이며 일반적으로 사용됩니다.
   3. 이항 힙:
      • 이론적 보장은 약간 더 우수하지만 구현이 더 복잡합니다.
   4. 피보나치 힙:
      • ( O(1) ) 상각 감소 키를 사용하면 이론상 최고의 성능을 발휘하지만 구현하기가 더 어렵습니다.
   5. 페어링 힙:
      • 간단하고 실제로 피보나치 힙에 가까운 성능을 발휘합니다.

   결론

   Dijkstra의 알고리즘은 음수가 아닌 가중치를 갖는 그래프에서 최단 경로를 찾는 강력하고 효율적인 방법입니다. 제한 사항(예: 음의 에지 가중치를 처리할 수 없음)이 있지만 네트워킹, 라우팅 및 기타 애플리케이션에서 널리 사용됩니다.

   • 휴식은 경로를 반복적으로 업데이트하여 최단 거리를 보장합니다.
   • 우선순위 대기열은 항상 가장 가까운 노드를 처리하고 정확성을 유지하도록 보장합니다.
   • 정확성은 유도를 통해 입증됩니다. 노드의 거리가 확정되면 최단 경로가 보장됩니다.

   ---

   다음은 엄격한 증명 및 예시와 함께 Dijkstra의 알고리즘을 탐색할 수 있는 몇 가지 자세한 리소스입니다.

   • 다익스트라 알고리즘 PDF
   • SlideShare의 최단 경로 알고리즘

   또한 Wikipedia는 해당 주제에 대한 훌륭한 개요를 제공합니다.

   인용:
   [1] https://www.fuhuthu.com/CPSC420F2019/dijkstra.pdf

   댓글로 여러분의 생각이나 개선 사항을 자유롭게 공유해 주세요!