Pohon spanning minimum vs Jalur terpendek

Apa perbedaan antara algoritma spanning tree minimum dan algoritma jalur terpendek?

Dalam kelas struktur data saya, kami membahas dua algoritma spanning tree minimum (Prim dan Kruskal) dan satu algoritma jalur terpendek (Dijkstra).

Minimum spanning tree adalah pohon dalam grafik yang membentang semua simpul dan berat total pohon minimal. Jalur terpendek cukup jelas, ini adalah jalur terpendek dari satu titik ke titik lainnya.

Apa yang saya tidak mengerti adalah karena pohon spanning minimum memiliki berat total minimal, bukankah jalan di pohon akan menjadi jalur terpendek? Adakah yang bisa menjelaskan apa yang saya lewatkan?

Bantuan apa pun dihargai.

$x,y,z$$\{x,y\},\{x,z\},\{y,z\}$$1$$\{x,y\},\{y,z\}$$\{x,z\}$

Kesimpulannya, jika Anda menempatkan semua jalur terpendek bersama, Anda tidak harus mendapatkan pohon.

Anda benar bahwa dua algoritma Dijkstra (jalur terpendek dari satu simpul mulai) dan Prim (pohon rentang berat minimum dimulai dari simpul yang diberikan) memiliki struktur yang sangat mirip. Keduanya serakah (mengambil sisi terbaik dari sudut pandang saat ini) dan membangun pohon yang membentang di grafik.

Nilai yang mereka minimalkan berbeda. Dijkstra memilih sebagai ujung berikutnya yang mengarah keluar dari pohon ke simpul yang belum dipilih paling dekat dengan simpul awal. (Kemudian dengan pilihan ini, jarak dihitung ulang.) Prim memilih sebagai ujung yang terpendek yang mengarah keluar dari pohon yang dibangun sejauh ini. Jadi, kedua algoritma memilih "batas minimal". Perbedaan utama adalah nilai yang dipilih menjadi minimal. Untuk Dijkstra itu adalah panjang jalur lengkap dari mulai node ke node kandidat, untuk Prim itu hanya berat dari tepi tunggal.

$x,y,z$$\{x,y\}$$\{x,z\}$$\{y,z\}$$x$$\{x,y\}$$\{x,z\}$$\{x,y\}$$\{y,z\}$

Sedangkan untuk Kruskal , itu sedikit berbeda. Ia memecahkan spanning tree minimal, tetapi selama eksekusi ia memilih edge yang mungkin tidak membentuk tree, mereka hanya menghindari siklus. Jadi solusi parsial dapat terputus. Pada akhirnya Anda mendapatkan pohon.

Meskipun perhitungan algoritma Minimum Spanning Tree dan Shortest Path terlihat serupa, mereka berfokus pada 2 persyaratan yang berbeda.

Dalam MST, persyaratan adalah untuk mencapai setiap simpul sekali (membuat pohon grafik) dan total (kolektif) biaya untuk mencapai setiap simpul harus minimum di antara semua kombinasi yang mungkin.

Dalam Jalur Terpendek, persyaratan adalah untuk mencapai titik tujuan dari titik sumber dengan biaya serendah mungkin (bobot terpendek). Jadi di sini kita tidak khawatir tentang mencapai setiap simpul melainkan hanya fokus pada simpul sumber dan tujuan dan di situlah letak perbedaannya.

Berikut adalah contoh untuk menjelaskan mengapa MST tidak selalu memberikan jalur terpendek antara 2 simpul.

(A)----5---(B)----5---(C)
 |                     |
 |----------7----------| 

Dalam kasus MST, tepi AB. BC akan berada di MST dengan berat total 10. Jadi biaya mencapai A ke C di MST adalah 10.

Tetapi dalam kasus Shortest Path, jalur terpendek antara A ke C adalah AC yang 7. AC tidak pernah di MST.

Perbedaannya terletak pada apa tujuan akhir dari algoritma ini-

Dijkstra's - Di sini tujuannya adalah untuk mencapai dari awal hingga akhir. Anda hanya khawatir tentang 2 poin ini, dan mengoptimalkan jalur Anda sesuai.

Krusal's - Di sini Anda dapat mulai dari titik mana pun dan harus mengunjungi semua titik lain dalam grafik. Jadi, Anda mungkin tidak selalu memilih jalur terpendek untuk dua poin. Alih-alih fokusnya adalah memilih jalur yang akan membawa Anda ke jalur yang lebih pendek untuk semua poin lainnya.

Saya pikir contoh akan membuatnya lebih jelas ..

Pohon spanning terlihat seperti di bawah ini. Ini karena jika kita menjumlahkan tepi dalam konfigurasi ini, kita mendapatkan biaya total seminimal mungkin : 2 + 5 + 14 + 4 = 25.

(1)   (4)
  \   /
   (2)
  /   \
(3)   (5)

Dengan mengamati pohon merentang, Anda mungkin salah berpikir bahwa itu memberi Anda jalan terpendek, tetapi dalam praktiknya tidak. Sebagai contoh Jika kita ingin beralih dari node (1)ke (4)yang akan dikenakan biaya 7. Namun jika kita menggunakan algoritma Dijkstra pada grafik asli, kita akan menemukan bahwa kita dapat langsung pergi dari node (1)ke (4)dengan biaya 5.

Contoh praktis untuk menunjukkan perbedaan>

Misalkan Anda tiba dengan kereta api di kota dan ingin pergi ke hotel Anda.

Opsi 1: Dapatkan taksi: Taksi akan mengambil jalur terpendek ke hotel Anda dari stasiun. Jika pengemudi harus mengikuti jalur di sepanjang pohon jalur terpendek yang berpusat di stasiun.

Opsi 2: Naik bus. Perusahaan bus ingin melayani mungkin orang, bukan hanya Anda. Jalur ideal akan mengambil semua poin penting di kota. Jadi itu akan mengikuti (*) jalan di sepanjang pohon spanning minimum. Itu sebabnya bus lebih lambat, tetapi karena biaya dibagi, itu lebih murah.

(*) Sebenarnya orang akan mengeluh jika pohon spanning minimum digunakan (perjalanan bus akan terlalu lama). Jadi dalam praktiknya itu akan menjadi solusi campuran dan akan menggunakan Pohon-Alpha (setengah jalan antara pohon rentang minimum dan pohon jalur terpendek).

Mereka didasarkan pada dua sifat yang berbeda. Minimum spanning tree didasarkan pada properti potong sedangkan jalur terpendek didasarkan pada properti edge edge.

Potongan membagi grafik menjadi dua komponen. Ini mungkin melibatkan banyak sisi. Di MST, kami memilih tepi dengan bobot paling sedikit.

Edge relaxing mengatakan bahwa mengingat saya tahu jarak antara A dan B: dist (a, b) dan dist antara A dan C: dist (a, c), jika dist (a, b) + edge (b, c) kurang dari dist (a, c), maka saya bisa bersantai edge (ac). Setelah merilekskan semua sisi, kami mendapatkan jalur terpendek.

Saya sangat merekomendasikan menonton video pada algoritma grafik dari profesor Robert Sedgewick.