Algoritma Jalan Terpendek Dijkstra - Pengenalan Terperinci dan Visual

Pengaturcaraan

Selamat Datang! Sekiranya anda selalu ingin mempelajari dan memahami algoritma Dijkstra, maka artikel ini sesuai untuk anda. Anda akan melihat bagaimana ia berfungsi di belakang tabir dengan penjelasan grafik langkah demi langkah.

Awak akan belajar:

  • Konsep Grafik Asas (tinjauan ringkas).
  • Algoritma Dijkstra digunakan untuk apa.
  • Bagaimana ia berfungsi di belakang tabir dengan contoh langkah demi langkah.

Mari kita mulakan. ✨

? Pengenalan kepada Grafik

Mari kita mulakan dengan pengenalan ringkas mengenai grafik.

Konsep asas

Grafik adalah struktur data yang digunakan untuk mewakili "hubungan" antara pasangan unsur.

  • Unsur-unsur ini dipanggil nod . Mereka mewakili objek, orang, atau entiti kehidupan sebenar.
  • Sambungan antara nod dipanggil tepi .

Ini adalah gambaran grafik dari grafik:

Nod diwakili dengan lingkaran berwarna dan tepi diwakili dengan garis yang menghubungkan bulatan ini.

? Petua: Dua nod disambungkan jika terdapat tepi di antara keduanya.

Permohonan

Grafik secara langsung berlaku untuk senario dunia nyata. Sebagai contoh, kita dapat menggunakan grafik untuk memodelkan rangkaian pengangkutan di mana simpul akan mewakili kemudahan yang mengirim atau menerima produk dan tepi akan mewakili jalan atau jalan yang menghubungkannya (lihat di bawah).

Jenis Grafik

Grafik boleh:

  • Tidak diarahkan: jika untuk setiap pasangan nod yang bersambung, anda boleh pergi dari satu nod ke yang lain dalam kedua arah.
  • Diarahkan: jika untuk setiap pasangan nod yang disambungkan, anda hanya boleh pergi dari satu simpul ke nod yang lain dalam arah tertentu. Kami menggunakan anak panah dan bukannya garis sederhana untuk mewakili tepi yang diarahkan.

? Petua: dalam artikel ini, kami akan bekerja dengan grafik yang tidak diarahkan .

Graf wajaran

A Graf berat badan adalah graf yang tepi mempunyai "badan" atau "kos". Berat tepi dapat mewakili jarak, waktu, atau apa sahaja yang memodelkan "sambungan" antara pasangan nod yang disambungkannya.

Contohnya, dalam graf berwajaran di bawah, anda dapat melihat nombor biru di sebelah setiap tepi. Nombor ini digunakan untuk mewakili berat tepi yang sepadan.

? Petua: Berat ini penting untuk Algoritma Dijkstra. Anda akan melihat mengapa hanya dalam sekejap.

? Pengenalan Algoritma Dijkstra

Sekarang setelah anda mengetahui konsep asas grafik, mari mulakan peneroka algoritma yang menakjubkan ini.

  • Tujuan dan Kes Penggunaan
  • Sejarah
  • Asas Algoritma
  • Keperluan

Tujuan dan Kes Penggunaan

Dengan Algoritma Dijkstra, anda dapat mencari jalan terpendek antara nod dalam graf. Terutama, anda dapat mencari jalan terpendek dari nod (disebut "node sumber") ke semua nod lain dalam grafik , menghasilkan pokok jalan terpendek.

Algoritma ini digunakan dalam peranti GPS untuk mencari jalan terpendek antara lokasi semasa dan destinasi. Ini memiliki aplikasi yang luas dalam industri, terutama dalam domain yang memerlukan jaringan pemodelan.

Sejarah

Algoritma ini dibuat dan diterbitkan oleh Dr. Edsger W. Dijkstra, seorang saintis komputer dan jurutera perisian Belanda yang cemerlang.

Pada tahun 1959, ia menerbitkan artikel 3 halaman yang berjudul "Catatan mengenai dua masalah dalam hubungan dengan grafik" di mana dia menjelaskan algoritma barunya.

Semasa wawancara pada tahun 2001, Dr. Dijkstra mendedahkan bagaimana dan mengapa dia merancang algoritma:

Apakah cara terpendek untuk melakukan perjalanan dari Rotterdam ke Groningen? Ini adalah algoritma untuk jalan terpendek, yang saya reka dalam masa lebih kurang 20 minit. Suatu pagi saya berbelanja di Amsterdam dengan tunangan muda saya, dan penat, kami duduk di teres kafe untuk minum secawan kopi dan saya hanya memikirkan sama ada saya boleh melakukan ini, dan kemudian saya merancang algoritma untuk jalan terpendek . Seperti yang saya katakan, ini adalah penemuan selama 20 minit. Sebenarnya, ia diterbitkan pada tahun 1959, tiga tahun kemudian. Penerbitannya masih cukup bagus. Salah satu sebab mengapa sangat bagus adalah kerana saya merancangnya tanpa pensil dan kertas. Tanpa pensil dan kertas anda hampir terpaksa mengelakkan semua kerumitan yang dapat dihindari. Akhirnya algoritma itu menjadi, saya kagum, salah satu landasan kemasyhuran saya. - Seperti yang dipetik dalam artikel Edsger W.Dijkstra dari temu ramah dengan Edsger W. Dijkstra.

⭐ Tidak boleh dipercayai, bukan? Hanya dalam 20 minit, Dr. Dijkstra merancang salah satu algoritma paling terkenal dalam sejarah Sains Komputer.

Asas Algoritma Dijkstra

  • Algoritma Dijkstra pada dasarnya bermula pada nod yang anda pilih (node ​​sumber) dan ia menganalisis grafik untuk mencari jalan terpendek antara nod itu dan semua nod lain dalam grafik.
  • Algoritma ini mengesan jarak terpendek yang diketahui dari setiap nod ke node sumber dan ia mengemas kini nilai-nilai ini jika ia menemui jalan yang lebih pendek.
  • Setelah algoritma menemui jalan terpendek antara simpul sumber dan nod lain, simpul tersebut ditandai sebagai "dikunjungi" dan ditambahkan ke jalan.
  • Proses berlanjutan sehingga semua nod dalam grafik telah ditambahkan ke jalan. Dengan cara ini, kita mempunyai jalan yang menghubungkan simpul sumber ke semua nod lain mengikuti jalan sesingkat mungkin untuk mencapai setiap nod.

Keperluan

Algoritma Dijkstra hanya dapat berfungsi dengan graf yang mempunyai bobot positif . Ini kerana, semasa proses, berat tepi harus ditambah untuk mencari jalan terpendek.

Sekiranya terdapat berat badan negatif dalam grafik, maka algoritma tidak akan berfungsi dengan baik. Setelah simpul ditandai sebagai "dikunjungi", jalan semasa ke simpul tersebut ditandai sebagai jalan terpendek untuk mencapai nod tersebut. Dan bobot negatif dapat mengubah ini jika berat keseluruhan dapat dikurangkan setelah langkah ini berlaku.

? Contoh Algoritma Dijkstra

Sekarang setelah anda mengetahui lebih lanjut mengenai algoritma ini, mari kita lihat bagaimana ia berfungsi di belakang tabir dengan contoh langkah demi langkah.

Kami mempunyai grafik ini:

Algoritma akan menghasilkan jalan terpendek dari nod 0ke semua nod lain dalam grafik.

? Petua: Untuk grafik ini, kita akan menganggap bahawa berat tepi mewakili jarak antara dua nod.

Kita akan mempunyai jalan terpendek dari simpul 0ke simpul 1, dari simpul 0ke simpul 2, dari simpul 0ke nod 3, dan seterusnya untuk setiap nod dalam grafik.

Pada mulanya, kami mempunyai senarai jarak ini (sila lihat senarai di bawah):

  • Jarak dari nod sumber ke dirinya adalah 0. Untuk contoh ini, simpul sumber akan menjadi simpul 0tetapi ia boleh menjadi simpul yang anda pilih.
  • Jarak dari nod sumber ke semua nod lain belum ditentukan, jadi kami menggunakan simbol infiniti untuk mewakili ini pada awalnya.

Kami juga mempunyai senarai ini (lihat di bawah) untuk mengesan node yang belum dikunjungi (simpul yang belum dimasukkan ke dalam jalan):

? Petua: Ingat bahawa algoritma selesai setelah semua nod telah ditambahkan ke jalan.

Oleh kerana kita memilih untuk memulakan di simpul 0, kita dapat menandai simpul ini sebagai dikunjungi. Sama dengan itu, kita mencarinya dari senarai nod yang tidak dilawati dan menambahkan sempadan merah ke nod yang sesuai dalam rajah:

Sekarang kita perlu mula memeriksa jarak dari nod 0ke nod bersebelahannya. Seperti yang anda lihat, ini adalah nod 1dan 2(lihat tepi merah):

? Petua: Ini tidak bermaksud bahawa kita segera menambahkan dua nod bersebelahan ke jalan terpendek. Sebelum menambahkan simpul ke jalan ini, kita perlu memeriksa sama ada kita telah menemui jalan terpendek untuk mencapainya. Kami hanya membuat proses pemeriksaan awal untuk melihat pilihan yang ada.

Kita perlu mengemas kini jarak dari simpul 0ke nod 1dan simpul 2dengan berat tepi yang menghubungkannya ke nod 0(simpul sumber). Berat ini masing-masing 2 dan 6:

Setelah mengemas kini jarak nod yang bersebelahan, kita perlu:

  • Pilih nod yang paling hampir dengan nod sumber berdasarkan jarak semasa yang diketahui.
  • Tandakan sebagai dilawati.
  • Tambahkan ke jalan.

Sekiranya kita memeriksa senarai jarak, kita dapat melihat bahawa simpul 1mempunyai jarak terpendek ke simpul sumber (jarak 2), jadi kita menambahkannya ke jalur.

Dalam rajah, kita dapat menggambarkannya dengan tepi merah:

Kami menandainya dengan kotak merah dalam senarai untuk menunjukkan bahawa ia telah "dikunjungi" dan bahawa kami telah menemui jalan terpendek ke nod ini:

Kami mencoretnya dari senarai nod yang tidak dilawati:

Sekarang kita perlu menganalisis nod bersebelahan baru untuk mencari jalan terpendek untuk mencapainya. Kami hanya akan menganalisis nod yang bersebelahan dengan nod yang sudah menjadi bahagian jalan terpendek (jalur yang ditandai dengan tepi merah).

Node 3dan simpul 2kedua-duanya bersebelahan dengan nod yang sudah berada di jalan kerana secara langsung disambungkan ke nod 0dan nod 1, seperti yang anda lihat di bawah. Inilah node yang akan kami analisis pada langkah seterusnya.

Oleh kerana kita sudah mempunyai jarak dari simpul sumber ke simpul 2dalam senarai kita, kita tidak perlu mengemas kini jarak kali ini. Kita hanya perlu mengemas kini jarak dari nod sumber ke simpul (simpul 3) yang baru:

Jarak ini ialah 7 . Mari lihat mengapa.

Untuk mencari jarak dari simpul sumber ke simpul lain (dalam kes ini, simpul 3), kami menambah berat semua tepi yang membentuk jalan terpendek untuk mencapai nod itu:

  • Untuk simpul 3: jarak keseluruhan adalah 7 kerana kita menambah berat tepi yang membentuk jalur 0 -> 1 -> 3(2 untuk tepi 0 -> 1dan 5 untuk tepi 1 -> 3).

Sekarang kita mempunyai jarak ke simpul bersebelahan, kita harus memilih simpul mana yang akan ditambahkan ke jalan. Kita mesti memilih node yang tidak dikunjungi dengan jarak terpendek (yang diketahui sekarang) ke nod sumber.

Dari senarai jarak, kita dapat segera mengesan bahawa ini adalah simpul 2dengan jarak 6 :

Kami menambahkannya ke jalur secara grafik dengan sempadan merah di sekitar nod dan pinggir merah:

Kami juga menandainya sebagai dikunjungi dengan menambahkan petak merah kecil dalam senarai jarak dan mencoretnya dari senarai nod yang tidak dilawati:

Sekarang kita perlu mengulangi proses untuk mencari jalan terpendek dari simpul sumber ke simpul bersebelahan baru, iaitu simpul 3.

Anda dapat melihat bahawa kita mempunyai dua jalan yang mungkin 0 -> 1 -> 3atau 0 -> 2 -> 3. Mari lihat bagaimana kita dapat menentukan jalan mana yang terpendek.

Node 3sudah mempunyai jarak dalam senarai yang direkodkan sebelumnya ( 7, lihat senarai di bawah). Jarak ini adalah hasil dari langkah sebelumnya, di mana kami menambah bobot 5 dan 2 dari dua tepi yang perlu kami lalui untuk mengikuti jalan tersebut 0 -> 1 -> 3.

Tetapi sekarang kita mempunyai alternatif lain. Sekiranya kita memilih untuk mengikuti jalan 0 -> 2 -> 3, kita perlu mengikuti dua tepi 0 -> 2dan 2 -> 3dengan bobot 6 dan 8 ,masing-masing,yang mewakili jarak keseluruhan 14 .

Jelas, jarak pertama (sedia ada) lebih pendek (7 vs 14), jadi kami akan memilih untuk mengekalkan jalan asal 0 -> 1 -> 3. Kami hanya mengemas kini jarak jika laluan baru lebih pendek.

Oleh itu, kita menambah nod ini ke jalan yang menggunakan alternatif pertama: 0 -> 1 -> 3.

Kami menandakan nod ini sebagai dilawati dan mencoretnya dari senarai nod yang tidak dilawati:

Sekarang kita mengulangi prosesnya lagi.

Kita perlu memeriksa nod bersebelahan baru yang belum kita lawati selama ini. Kali ini, nod ini adalah simpul 4dan simpul 5kerana bersebelahan dengan nod 3.

Kami mengemas kini jarak node ini ke node sumber, sentiasa berusaha mencari jalan yang lebih pendek, jika mungkin:

  • Untuk simpul 4: jaraknya 17 dari jalan   0 -> 1 -> 3 -> 4.
  • Untuk nod 5: jaraknya 22 dari jalan 0 -> 1 -> 3 -> 5.

? Petua: Perhatikan bahawa kita hanya boleh mempertimbangkan untuk memperluas jalan terpendek (ditandai dengan warna merah). Kita tidak dapat mempertimbangkan jalan yang akan membawa kita melalui tepi yang belum ditambahkan ke jalan terpendek (misalnya, kita tidak dapat membentuk jalan yang melewati tepi 2 -> 3).

Kita perlu memilih node yang tidak dikunjungi yang akan ditandai sebagai dikunjungi sekarang. Dalam kes ini, simpul 4kerana mempunyai jarak terpendek dalam senarai jarak. Kami menambahkannya secara grafik dalam rajah:

Kami juga menandainya sebagai "dikunjungi" dengan menambahkan kotak merah kecil dalam senarai:

Dan kami mencoretnya dari senarai nod yang tidak dilawati:

Dan kami mengulangi proses itu sekali lagi. Kami memeriksa nod bersebelahan: nod 5dan nod 6. Kita perlu menganalisis setiap jalan yang mungkin kita ikuti untuk mencapainya dari simpul yang sudah ditandai sebagai dilawati dan ditambahkan ke jalan tersebut.

Untuk nod 5:

  • Pilihan pertama adalah mengikuti jalan 0 -> 1 -> 3 -> 5, yang mempunyai jarak 22 dari simpul sumber (2 + 5 + 15). Jarak ini sudah tercatat dalam senarai jarak pada langkah sebelumnya.
  • Pilihan kedua adalah mengikuti jalan 0 -> 1 -> 3 -> 4 -> 5, yang memiliki jarak 23 dari simpul sumber (2 + 5 + 10 + 6).

Jelas, jalan pertama lebih pendek, jadi kami memilihnya untuk simpul 5.

Untuk nod 6:

  • Laluan yang tersedia adalah 0 -> 1 -> 3 -> 4 -> 6, yang mempunyai jarak 19 dari simpul sumber (2 + 5 + 10 + 2).

Kami menandakan simpul dengan jarak terpendek (kini diketahui) seperti yang dikunjungi. Dalam kes ini, nod 6.

Dan kami mencoretnya dari senarai nod yang tidak dilawati:

Sekarang kita mempunyai jalan ini (ditandai dengan warna merah):

Hanya satu nod yang belum dikunjungi, nod 5. Mari lihat bagaimana kita dapat memasukkannya ke jalan.

Terdapat tiga jalur berbeza yang dapat kita ambil untuk mencapai simpul 5dari nod yang telah ditambahkan ke jalan:

  • Pilihan 1:0 -> 1 -> 3 -> 5 dengan jarak 22 (2 + 5 + 15).
  • Pilihan 2:0 -> 1 -> 3 -> 4 -> 5 dengan jarak 23 (2 + 5 + 10 + 6).
  • Pilihan 3:0 -> 1 -> 3 -> 4 -> 6 -> 5 dengan jarak 25 (2 + 5 + 10 + 2 + 6).

Kami memilih jalan terpendek: 0 -> 1 -> 3 -> 5dengan jarak 22 .

Kami menandakan nod sebagai dilawati dan mencoretnya dari senarai nod yang tidak dilawati:

Dan voilà! Kami mempunyai hasil akhir dengan jalan terpendek dari nod 0ke setiap nod dalam grafik.

Dalam rajah, garis merah menandakan tepi yang tergolong dalam jalan terpendek. Anda perlu mengikuti pinggir ini untuk mengikuti jalan terpendek untuk mencapai simpul tertentu dalam grafik bermula dari nod 0.

Sebagai contoh, jika anda ingin mencapai simpul 6bermula dari simpul 0, anda hanya perlu mengikuti tepi merah dan anda akan mengikuti jalan terpendek 0 -> 1 -> 3 -> 4 - > 6secara automatik.

? Ringkasnya

  • Grafik digunakan untuk memodelkan hubungan antara objek, orang, atau entiti. Mereka mempunyai dua elemen utama: simpul dan tepi. Nod mewakili objek dan tepi mewakili hubungan antara objek ini.
  • Algoritma Dijkstra mencari jalan terpendek antara nod tertentu (yang disebut "node sumber") dan semua nod lain dalam grafik.
  • Algoritma ini menggunakan bobot tepi untuk mencari jalan yang meminimumkan jumlah jarak (berat) antara nod sumber dan semua nod lain.

Saya sangat berharap anda menyukai artikel saya dan menganggapnya berguna. Sekarang anda tahu bagaimana Algoritma Dijkstra berfungsi di belakang tabir. Ikuti saya di Twitter @EstefaniaCassN dan lihat kursus dalam talian saya.