Memahami Algoritma Dijkstra: Dari Teori kepada Perlaksanaan

Algoritma Dijkstra ialah algoritma pencarian laluan klasik yang digunakan dalam teori graf untuk mencari laluan terpendek dari nod sumber ke semua nod lain dalam graf. Dalam artikel ini, kami akan meneroka algoritma, bukti ketepatannya dan menyediakan pelaksanaan dalam JavaScript.

Apakah Algoritma Dijkstra?

Algoritma Dijkstra ialah algoritma tamak yang direka untuk mencari laluan terpendek daripada satu nod sumber dalam graf berwajaran dengan pemberat tepi bukan negatif. Ia telah dicadangkan oleh Edsger W. Dijkstra pada tahun 1956 dan kekal sebagai salah satu algoritma yang paling banyak digunakan dalam sains komputer.

Input dan Output

• Input: Satu graf $G=(V,E)$G=(V,E) , di mana $V$V ialah set bucu, $E$E ialah set tepi, dan nod sumber $s\in V$s∈V .
• Output: Jarak laluan terpendek dari $s$s kepada semua nod lain dalam $V$V .

Konsep Teras

1. Relaksasi: Proses mengemas kini jarak terpendek yang diketahui ke nod.
2. Baris Gilir Keutamaan: Mengambil nod dengan jarak tentatif terkecil dengan cekap.
3. Pendekatan Tamak: Memproses nod dalam susunan tidak menurun bagi jarak terpendeknya.

Algoritma

1. Mulakan jarak:
   

   $$\text{dist}(s)=0,\text{dist}(v)=\mathrm{\infty }\mathrm{\forall }v\mathrm{\ne }s$$dist(s)=0,dist(v)=∞∀v=s

2. Gunakan baris gilir keutamaan untuk menyimpan nod berdasarkan jaraknya.

3. Berulang kali keluarkan nod dengan jarak terkecil dan rilekskan jirannya.

Relaksasi - Penjelasan Matematik

• Permulaan: $\text{dist}(s)=0,\text{dist}(v)=\mathrm{\infty }\text{untuk semua}v\mathrm{\ne }s$dist(s)=0,dist(v)=∞untuk a llv=s

di mana $(s)$(s) ialah nod sumber, dan $(v)$(v) mewakili mana-mana nod lain.

• Langkah Relaksasi: untuk setiap tepi $(u,v)$(u,v) dengan berat $w(u,v)$w(u,v) : Jika $\text{dist}(v)>\text{dist}(u)w(u,v)$dist(v)>dist (u) w(u,v) , kemas kini:
  $$\text{dist}(v)=\text{dist}(u)w(u,v),\text{sebelumnya}(v)=u$$dist(v)=dist(u) w(u,v),sebelumnya(v)=u

Mengapa Ia Berfungsi: Relaksasi memastikan kami sentiasa mencari laluan terpendek ke nod dengan mengemas kini jarak secara berperingkat apabila laluan yang lebih pendek ditemui.

Barisan Keutamaan - Penjelasan Matematik

• Operasi Beratur:

  • Baris gilir keutamaan sentiasa menyah gilir nod $(u)$(u) dengan jarak tentatif terkecil:
    $$u=\arg \underset{v\in Q}{\min }\text{dist}(v)$$u=argv∈Q min​dist(v)
  • Mengapa Ia Berfungsi: Dengan memproses nod dengan yang terkecil $(\text{dist}(v))$(dist(v)) , kami menjamin laluan terpendek dari sumber ke $(u)$(u) .

Bukti Ketepatan

Kami membuktikan ketepatan algoritma Dijkstra menggunakan aruhan kuat.

Apakah Induksi Kuat?

Aruhan kuat ialah varian aruhan matematik di mana, untuk membuktikan pernyataan $(P(n))$(P(n)) , kami menganggap kebenaran $(P(1),P(2),\dots ,P(k))$(P(1),P(2),…,P(k)) untuk membuktikan $(P(k1))$( P(k 1)) . Ini berbeza daripada induksi biasa, yang menganggap sahaja $(P(k))$(P(k)) untuk membuktikan $(P(k1))$( P(k 1)) . Terokainya dengan lebih terperinci dalam siaran saya yang lain.

Ketepatan Algoritma Dijkstra (Bukti Induktif)

1. Kes Asas:
   
   Nod sumber $(s)$(s) dimulakan dengan $\text{dist}(s)=0$dist(s)=0 , yang betul.

2. Hipotesis Induktif:
   
   Andaikan semua nod yang diproses setakat ini mempunyai jarak laluan terpendek yang betul.

3. Langkah Induktif:
   
   Nod seterusnya $(u)$(u) disingkirkan daripada barisan keutamaan. Sejak $\text{dist}(u)$dist(u) ialah jarak terkecil yang tinggal, dan semua nod sebelumnya mempunyai jarak yang betul, $\text{dist}(u)$dist(u) juga betul.

Pelaksanaan JavaScript

Prasyarat (Baris Gilir Keutamaan):

// 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;
  }
}

Berikut ialah pelaksanaan JavaScript bagi algoritma Dijkstra menggunakan baris gilir keutamaan:

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);

Bina Semula Laluan

// 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;
  }
}

Contoh Panduan

Perwakilan Graf

• Nod: $A,B,C,D$A,B,C,D
• Tepi:
  • $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)
  • $C\to D=(1)$C→D=(1)

Langkah demi Langkah Pelaksanaan

1. Mulakan jarak:
   

   $$\text{dist}(A)=0,\text{dist}(B)=\mathrm{\infty },\text{dist}(C)=\mathrm{\infty },\text{dist}(D)=\mathrm{\infty }$$dist(A)=0,dist(B)= ∞,dist(C)=∞,dist(D)=∞

2. Proses A:

   • Tepi santai: $A\to B,A\to C\mathrm{.}$A→B,A→C.
     $$\text{dist}(B)=1,\text{dist}(C)=4$$dist(B)=1,dist(C)=4

3. Proses B:

   • Tepi santai: $B\to C,B\to D\mathrm{.}$B→C,B→D.
     $$\text{dist}(C)=3,\text{dist}(D)=6$$dist(C)=3,dist(D)=6

4. Proses C:

   • Tepi santai: $C\to D\mathrm{.}$C→D.
     $$\text{dist}(D)=4$$dist(D)=4

5. Proses D:

   • Tiada kemas kini lanjut.

Jarak dan Laluan Akhir

Pengoptimuman dan Kerumitan Masa

Membandingkan kerumitan masa algoritma Dijkstra dengan pelaksanaan baris gilir keutamaan yang berbeza:

Perkara Utama:

1. Tatasusunan Mudah:
   • Tidak cekap untuk graf besar kerana carian linear untuk ekstrak-min.
2. Timbunan Binari:
   • Standard dan biasa digunakan kerana keseimbangan kesederhanaan dan kecekapannya.
3. Timbunan Binomial:
   • Jaminan teori yang lebih baik sedikit tetapi lebih kompleks untuk dilaksanakan.
4. Timbunan Fibonacci:
   • Prestasi teori terbaik dengan kunci penurunan terlunas ( O(1) ) tetapi lebih sukar untuk dilaksanakan.
5. Timbunan Berpasangan:
   • Mudah dan berprestasi hampir dengan timbunan Fibonacci dalam amalan.

Kesimpulan

Algoritma Dijkstra ialah kaedah yang berkuasa dan cekap untuk mencari laluan terpendek dalam graf dengan pemberat bukan negatif. Walaupun ia mempunyai had (cth., tidak boleh mengendalikan pemberat tepi negatif), ia digunakan secara meluas dalam rangkaian, penghalaan dan aplikasi lain.

• Relaksasi memastikan jarak terpendek dengan mengemas kini laluan secara berulang.
• Baris Gilir Keutamaan menjamin kami sentiasa memproses nod terdekat, mengekalkan ketepatan.
• Ketepatan dibuktikan melalui aruhan: Sebaik sahaja jarak nod dimuktamadkan, ia dijamin sebagai laluan terpendek.

Berikut ialah beberapa sumber terperinci di mana anda boleh meneroka algoritma Dijkstra bersama-sama dengan bukti dan contoh yang ketat:

• PDF Algoritma Dijkstra
• Algoritma Laluan Terpendek pada SlideShare

Selain itu, Wikipedia menawarkan gambaran keseluruhan topik yang hebat.

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

Jangan ragu untuk berkongsi pendapat atau penambahbaikan anda dalam ulasan!

Atas ialah kandungan terperinci Memahami Algoritma Dijkstra: Dari Teori kepada Perlaksanaan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!