Bi Directional Dijkstra

Dijkstra dua arah

Masalah

Diberikan grafik dengan bobot tepi non-negatif, titik titik sumber dan target vertec t . Temukan jalan terpendek antara S dan T

Tapi mengapa kita tidak menggunakan algoritma Dijkstra hanya untuk menyelesaikan masalah?

0 (E + VLOGV) adalah kompleksitas waktu terburuk dari algoritma Dijkstra yang cukup cepat. Tapi, untuk grafik dengan 20 juta simpul dan 50 juta tepi, itu akan bekerja selama beberapa detik rata -rata. Jadi, kita membutuhkan sesuatu yang jauh lebih cepat.

Sebelum kita masuk ke detail pencarian dua arah, mari kita jelajahi konsep "enam derajat pemisahan"

• Pada tahun 1929, seorang penulis Hongaria, Frigyes Karinthy untuk pertama kalinya mengusulkan konsep "enam derajat pemisahan" dalam rantai cerita pendeknya.
• Enam derajat pemisahan adalah gagasan bahwa semua makhluk hidup dan segala sesuatu di dunia ini berjarak enam langkah atau lebih sedikit dari satu sama lain.

Sekarang, mari kita lihat jejaring sosial paling populer, Facebook. Misalkan rata -rata orang di Facebook memiliki sekitar 100 teman. Kemudian, jika kita mempertimbangkan teman -teman dari orang itu, itu akan menjadi 100*100 itu adalah 10.000 teman teman. Jika kami mempertimbangkan "teman teman teman" , itu akan menjadi 100 kali lebih atau 1 juta. Dan jika kita melanjutkan enam kali kita akan memiliki 1 triliun orang.

Namun, populasi global adalah 7,6 miliar.

Sekarang, bagaimana kita menemukan jalur terpendek antara dua orang acak A dan B melalui koneksi mereka di jejaring sosial?

Mari kita pertimbangkan pencarian dua arah. Jadi kita akan mempertimbangkan teman -teman teman dari A dan teman -teman teman B.

Perhatikan bahwa kita akan memiliki sekitar 1 juta teman teman teman untuk A dan B. jadi, secara total kita hanya akan mempertimbangkan 2 juta orang dalam kasus ini.

Algoritma Normal Dijkstra harus terlihat kira -kira 2 miliar orang di jejaring sosial untuk menemukan jalur terpendek antara A dan B.

Apa itu pencarian dua arah

Dalam hal ini, kami menjalankan dua pencarian simultan: satu maju dari keadaan awal, dan satu ke belakang dari gawang, berhenti ketika keduanya bertemu di tengah.

Pseudocode untuk dua arah Dijkstra pada grafik g

• Bangun GR (grafik terbalik)
• Mulai Dijkstra dari S (Sumber) di G dan dari T (Target) di GR
• Bergantian antara langkah -langkah Dijkstra di G dan di GR
• Berhenti ketika beberapa vertex "V" diproses baik dalam G dan GR.
• Hitung jalur terpendek antara S dan T.

Perhitungan jalur terpendek antara S dan T: Biarkan dist [u] menjadi perkiraan jarak dalam dijkstra ke depan dari S dalam G. Biarkan distr [u] menjadi perkiraan jarak dalam Dijkstra ke belakang dari T di GR. Setelah beberapa simpul "V" diproses baik dalam G dan GR, beberapa jalur terpendek dari S ke T melewati beberapa simpul "U" yang diproses baik dalam G, dalam GR atau keduanya dan D (S, T) = Dist [u] + distr [u]