Perbedaan antara algoritma Prim dan Dijkstra?

Apa perbedaan yang tepat antara algoritma Dijkstra dan Prim? Saya tahu Prim akan memberikan MST tetapi pohon yang dihasilkan oleh Dijkstra juga akan menjadi MST. Lalu apa perbedaan pastinya?

Algoritme Prim membangun pohon rentang minimum untuk grafik, yang merupakan pohon yang menghubungkan semua node dalam grafik dan memiliki biaya total paling sedikit di antara semua pohon yang menghubungkan semua node. Namun, panjang jalur antara dua node di MST mungkin bukan jalur terpendek antara dua node dalam grafik asli. MST berguna, misalnya, jika Anda ingin menyambungkan node dalam grafik secara fisik untuk menyediakan listrik kepada mereka dengan biaya total paling sedikit. Tidak masalah bahwa panjang jalur antara dua node mungkin tidak optimal, karena yang Anda pedulikan hanyalah fakta bahwa keduanya terhubung.

Algoritma Dijkstra membangun pohon jalur terpendek yang dimulai dari beberapa node sumber. Pohon jalur terpendek adalah pohon yang menghubungkan semua node dalam grafik kembali ke node sumber dan memiliki properti yang meminimalkan panjang jalur dari node sumber ke node lain dalam grafik. Ini berguna, misalnya, jika Anda ingin membangun jaringan jalan raya yang seefisien mungkin bagi setiap orang untuk mencapai beberapa landmark penting utama. Namun, pohon jalur terpendek tidak dijamin menjadi pohon rentang minimum, dan jumlah biaya di tepi pohon jalur terpendek bisa jauh lebih besar daripada biaya MST.

Perbedaan penting lainnya menyangkut jenis grafik apa yang dikerjakan algoritme. Algoritme Prim hanya berfungsi pada grafik yang tidak diarahkan, karena konsep MST mengasumsikan bahwa grafik secara inheren tidak diarahkan. (Ada sesuatu yang disebut "arborescence rentang minimum" untuk grafik terarah, tetapi algoritma untuk menemukannya jauh lebih rumit). Algoritma Dijkstra akan bekerja dengan baik pada grafik terarah, karena pohon jalur terpendek memang bisa diarahkan. Selain itu, algoritme Dijkstra tidak selalu menghasilkan solusi yang tepat dalam grafik yang berisi bobot tepi negatif , sedangkan algoritme Prim dapat menangani ini.

Semoga ini membantu!

Algoritme Dijkstra tidak membuat MST, ia menemukan jalur terpendek.

Pertimbangkan grafik ini

       5     5
  s *-----*-----* t
     \         /
       -------
         9

Jalur terpendek adalah 9, sedangkan MST adalah 'jalur' yang berbeda pada 10.

Algoritma Prim dan Dijkstra hampir sama, kecuali untuk "fungsi relaks".

Formal:

MST-PRIM (G, w, r) {
    for each key ∈ G.V
        u.key = ∞
        u.parent = NIL
    r.key = 0
    Q = G.V

    while (Q ≠ ø)
        u = Extract-Min(Q)
        for each v ∈ G.Adj[u]
            if (v ∈ Q)
                alt = w(u,v)    <== relax function, Pay attention here
                if alt < v.key
                    v.parent = u
                    v.key = alt
}

Dijkstra:

Dijkstra (G, w, r) {
    for each key ∈ G.V
        u.key = ∞
        u.parent = NIL
    r.key = 0
    Q = G.V

    while (Q ≠ ø)
        u = Extract-Min(Q)
        for each v ∈ G.Adj[u]
            if (v ∈ Q)
                alt = w(u,v) + u.key  <== relax function, Pay attention here
                if alt < v.key
                    v.parent = u
                    v.key = alt
}

Satu-satunya perbedaan ditunjukkan oleh panah, yaitu fungsi relaksasi.

• Prim, yang mencari pohon rentang minimum, hanya peduli tentang minimum total tepi yang menutupi semua simpul. Fungsi relaksasi adalahalt = w(u,v)
• Dijkstra, yang mencari panjang jalur minimum, jadi peduli dengan akumulasi tepi. Fungsi relaksasi adalahalt = w(u,v) + u.key

Algoritma Dijsktra menemukan jarak minimum dari node i ke semua node (Anda menentukan i). Jadi sebagai gantinya Anda mendapatkan pohon jarak minimum dari simpul i.

Algoritma prims memberi Anda pohon rentang minimum untuk grafik tertentu . Pohon yang menghubungkan semua node sedangkan jumlah semua biaya seminimal mungkin.

Jadi dengan Dijkstra Anda dapat beralih dari node yang dipilih ke node lain dengan biaya minimum , Anda tidak mendapatkan ini dengan Prim's

Satu-satunya perbedaan yang saya lihat adalah bahwa algoritma Prim menyimpan tepi biaya minimum sedangkan algoritma Dijkstra menyimpan total biaya dari simpul sumber ke simpul saat ini.

Dijkstra memberi Anda cara dari node sumber ke node tujuan sedemikian rupa sehingga biayanya minimum. Namun algoritme Prim memberi Anda pohon rentang minimum sehingga semua node terhubung dan total biaya minimum.

Dengan kata sederhana:

Jadi, jika Anda ingin menggunakan kereta untuk menghubungkan beberapa kota, Anda akan menggunakan algo Prim. Tetapi jika Anda ingin pergi dari satu kota ke kota lain untuk menghemat waktu sebanyak mungkin, Anda akan menggunakan algo Dijkstra.

Keduanya dapat diimplementasikan menggunakan algoritma generik yang sama persis sebagai berikut:

Inputs:
  G: Graph
  s: Starting vertex (any for Prim, source for Dijkstra)
  f: a function that takes vertices u and v, returns a number

Generic(G, s, f)
    Q = Enqueue all V with key = infinity, parent = null
    s.key = 0
    While Q is not empty
        u = dequeue Q
        For each v in adj(u)
            if v is in Q and v.key > f(u,v)
                v.key = f(u,v)
                v.parent = u

Untuk Prim, operan f = w(u, v)dan oper Dijkstra f = u.key + w(u, v).

Hal menarik lainnya adalah Generic di atas juga dapat mengimplementasikan Breadth First Search (BFS) meskipun akan berlebihan karena antrian prioritas yang mahal tidak terlalu dibutuhkan. Untuk mengubah algoritma Generik di atas ke BFS, lewati f = u.key + 1yang sama dengan memaksakan semua bobot ke 1 (yaitu BFS memberikan jumlah minimum edge yang diperlukan untuk melintasi dari titik A ke B).

Intuisi

Berikut satu cara yang baik untuk berpikir tentang algoritme umum di atas: Kita mulai dengan dua kelompok A dan B. Awalnya, letakkan semua simpul Anda di B sehingga keranjang A kosong. Kemudian kita pindahkan satu simpul dari B ke A. Sekarang lihat semua sisi dari simpul di A yang memotong ke simpul di B. Kita memilih satu sisi menggunakan beberapa kriteria dari tepi yang saling silang ini dan memindahkan simpul yang sesuai dari B ke A. Ulangi proses ini sampai B kosong.

Cara brute force untuk mengimplementasikan ide ini adalah dengan mempertahankan antrian prioritas dari edge untuk simpul di A yang memotong ke B. Jelas itu akan merepotkan jika grafik tidak jarang. Jadi pertanyaannya adalah bisakah kita mempertahankan antrian prioritas simpul? Ini sebenarnya kita bisa karena keputusan kita akhirnya adalah simpul mana yang harus dipilih dari B.

Konteks Sejarah

Sangat menarik bahwa versi generik dari teknik di balik kedua algoritme secara konseptual sudah berusia 1930 bahkan ketika komputer elektronik tidak ada.

Cerita dimulai dengan Otakar Borůvka yang membutuhkan algoritme untuk teman keluarga yang mencoba mencari cara untuk menghubungkan kota-kota di negara Moravia (sekarang bagian dari Republik Ceko) dengan saluran listrik berbiaya rendah. Dia menerbitkan algoritmanya pada tahun 1926 dalam jurnal yang berhubungan dengan matematika, karena Ilmu Komputer belum ada saat itu. Hal ini menjadi perhatian Vojtěch Jarník yang memikirkan perbaikan pada algoritme Borůvka dan menerbitkannya pada tahun 1930. Ia sebenarnya menemukan algoritme yang sama yang sekarang kita kenal sebagai algoritme Prim yang menemukannya kembali pada tahun 1957.

Terlepas dari semua ini, pada tahun 1956 Dijkstra perlu menulis program untuk mendemonstrasikan kemampuan komputer baru yang dikembangkan institutnya. Dia pikir akan menyenangkan memiliki komputer yang menemukan koneksi untuk bepergian antara dua kota di Belanda. Dia merancang algoritme dalam 20 menit. Dia membuat grafik 64 kota dengan beberapa penyederhanaan (karena komputernya 6-bit) dan menulis kode untuk komputer tahun 1956 ini. Namun dia tidak mempublikasikan algoritmanya karena pada dasarnya tidak ada jurnal ilmu komputer dan dia pikir ini mungkin tidak terlalu penting. Tahun berikutnya dia belajar tentang masalah menghubungkan terminal komputer baru sehingga panjang kabel diminimalkan. Dia memikirkan masalah ini dan menemukan kembali Jarník / Prim ' algoritma yang sekali lagi menggunakan teknik yang sama dengan algoritma jalur terpendek yang dia temukan setahun sebelumnya. Diamenyebutkan bahwa kedua algoritmanya dirancang tanpa menggunakan pena atau kertas. Pada tahun 1959 ia menerbitkan kedua algoritma tersebut dalam sebuah makalah yang panjangnya hanya 2 setengah halaman.

Dijkstra menemukan jalur terpendek antara simpul awal dan setiap simpul lainnya. Jadi sebagai imbalannya Anda mendapatkan pohon jarak minimum dari simpul awal yaitu Anda dapat menjangkau setiap simpul lainnya seefisien mungkin.

Algoritma prims memberi Anda MST untuk grafik yang diberikan, yaitu pohon yang menghubungkan semua node sementara jumlah semua biaya seminimal mungkin.

Untuk membuat cerita pendek dengan contoh realistis:

1. Dijkstra ingin mengetahui jalur terpendek ke setiap titik tujuan dengan menghemat waktu tempuh dan bahan bakar.
2. Prim ingin mengetahui cara menggunakan sistem rel kereta api secara efisien, yaitu menghemat biaya material.

Langsung dari artikel wikipedia Algoritma Dijkstra :

Proses yang mendasari algoritma Dijkstra mirip dengan proses greedy yang digunakan dalam algoritma Prim. Tujuan Prim adalah untuk menemukan pohon rentang minimum yang menghubungkan semua node dalam grafik; Dijkstra hanya memperhatikan dua node. Prim tidak mengevaluasi bobot total jalur dari node awal, hanya jalur individu.

Saya merasa terganggu dengan pertanyaan yang sama belakangan ini, dan saya pikir saya mungkin akan berbagi pemahaman saya ...

Saya pikir perbedaan utama antara kedua algoritma ini (Dijkstra dan Prim) berakar pada masalah yang mereka rancang untuk pecahkan, yaitu, jalur terpendek antara dua node dan pohon rentang minimal (MST). Formalnya adalah menemukan jalur terpendek antara say, node s dan t , dan persyaratan rasionalnya adalah mengunjungi setiap tepi grafik paling banyak sekali. Namun, TIDAK mengharuskan kita mengunjungi semua node. Yang terakhir (MST) adalah membuat kita mengunjungi SEMUA node (paling banyak sekali), dan dengan persyaratan rasional yang sama untuk mengunjungi setiap tepi paling banyak sekali juga.

Meski begitu, Dijkstra memungkinkan kita untuk "mengambil jalan pintas" selama saya bisa dari s ke t , tanpa mengkhawatirkan konsekuensinya - begitu saya sampai ke t , saya selesai! Meskipun ada juga jalur dari s ke t di MST, namun jalur s - t ini dibuat dengan pertimbangan semua node lainnya, oleh karena itu jalur ini bisa lebih panjang dari jalur s - t yang ditemukan oleh algoritma Dijstra. Di bawah ini adalah contoh singkat dengan 3 node:

                                  2       2  
                          (s) o ----- o ----- o (t)     
                              |               |
                              -----------------
                                      3

Misalkan masing-masing tepi atas bernilai 2, dan tepi bawah bernilai 3, maka Dijktra akan memberi tahu kita untuk mengambil jalur bawah, karena kita tidak peduli dengan simpul tengah. Di sisi lain, Prim akan mengembalikan kita MST dengan 2 tepi atas, membuang tepi bawah.

Perbedaan tersebut juga tercermin dari perbedaan halus dalam implementasi: dalam algoritma Dijkstra, seseorang perlu memiliki langkah pembukuan (untuk setiap node) untuk memperbarui jalur terpendek dari s , setelah menyerap node baru, sedangkan dalam algoritma Prim, ada tidak ada kebutuhan seperti itu.

Perbedaan utama antara algoritme dasar terletak pada kriteria pemilihan tepi yang berbeda. Umumnya, mereka berdua menggunakan antrian prioritas untuk memilih node berikutnya, tetapi memiliki kriteria berbeda untuk memilih node yang berdekatan dari node pemrosesan saat ini: Algoritma Prim mengharuskan node yang berdekatan berikutnya juga harus disimpan dalam antrian, sedangkan Algoritma Dijkstra tidak:

def dijkstra(g, s):
    q <- make_priority_queue(VERTEX.distance)
    for each vertex v in g.vertex:
        v.distance <- infinite
        v.predecessor ~> nil
        q.add(v)
    s.distance <- 0
    while not q.is_empty:
        u <- q.extract_min()
        for each adjacent vertex v of u:
            ...

def prim(g, s):
    q <- make_priority_queue(VERTEX.distance)
    for each vertex v in g.vertex:
        v.distance <- infinite
        v.predecessor ~> nil
        q.add(v)
    s.distance <- 0
    while not q.is_empty:
        u <- q.extract_min()
        for each adjacent vertex v of u:
            if v in q and weight(u, v) < v.distance:// <-------selection--------
            ...

Perhitungan vertex. Jarak adalah titik berbeda kedua.

Algoritme Dijkstra adalah masalah jalur terpendek sumber tunggal antara node i dan j, tetapi algoritme Prim merupakan masalah pohon rentang terpendek yang minimal. Algoritma ini menggunakan konsep pemrograman yang disebut 'algoritma rakus'.

Jika Anda memeriksa gagasan ini, silakan kunjungi

1. Catatan kuliah algoritma serakah: http://jeffe.cs.illinois.edu/teaching/algorithms/notes/07-greedy.pdf
2. Pohon rentang minimum: http://jeffe.cs.illinois.edu/teaching/algorithms/notes/20-mst.pdf
3. Jalur terpendek sumber tunggal: http://jeffe.cs.illinois.edu/teaching/algorithms/notes/21-sssp.pdf

Algoritma Dijkstras hanya digunakan untuk mencari jalur terpendek.

Dalam pohon Rentang Minimum (algoritma Prim atau Kruskal) Anda mendapatkan egdes minimum dengan nilai tepi minimum.

Sebagai contoh: - Pertimbangkan situasi di mana Anda tidak ingin membuat jaringan besar di mana Anda akan membutuhkan sejumlah besar kabel sehingga penghitungan kabel ini dapat dilakukan menggunakan Pohon Rentang Minimum (algoritma Prim atau Kruskal) (yaitu akan memberi Anda jumlah kabel minimum untuk membuat koneksi jaringan kabel besar dengan biaya minimum).

Sedangkan "Algoritma Dijkstras" akan digunakan untuk mendapatkan jalur terpendek antara dua node sekaligus menghubungkan setiap node satu sama lain.

Penjelasan paling sederhana adalah di Prims Anda tidak menentukan Starting Node , tetapi di dijsktra Anda (Perlu memiliki node awal) harus menemukan jalur terpendek dari node yang diberikan ke semua node lainnya.

@templatetypedef telah membahas perbedaan antara MST dan jalur terpendek. Saya telah membahas perbedaan algoritme di tempat lain. Jadi, jawablah dengan mendemonstrasikan bahwa keduanya dapat diimplementasikan menggunakan algoritme umum yang sama yang mengambil satu parameter lagi sebagai input: fungsi f(u,v). Perbedaan antara algoritma Prim dan Dijkstra adalah yang f(u,v)Anda gunakan.

Pada level kode, perbedaan lainnya adalah API.

Anda menginisialisasi Prim dengan simpul sumber, s , ie Prim.new(s),; s dapat berupa simpul manapun, dan terlepas dari s , hasil akhirnya, yang merupakan tepi dari pohon rentang minimum (MST) adalah sama. Untuk mendapatkan tepi MST, kami memanggil metode tersebut edges().

Anda menginisialisasi Dijkstra dengan simpul sumber, s , yaitu, Dijkstra.new(s)Anda ingin mendapatkan jalur / jarak terpendek ke semua simpul lainnya. Hasil akhirnya, yang merupakan jalur / jarak terpendek dari s ke semua simpul lainnya; berbeda tergantung pada s . Untuk mendapatkan jalur / jarak terpendek dari s ke sembarang simpul, v , kita memanggil metode distanceTo(v)dan pathTo(v)masing - masing.