Bagaimana cara Pencarian Breadth-First saat mencari Jalur Terpendek?

129

Saya telah melakukan beberapa penelitian, dan sepertinya saya kehilangan satu bagian kecil dari algoritma ini. Saya mengerti bagaimana Pencarian Lebar-Pertama bekerja, tapi saya tidak mengerti bagaimana persisnya itu akan membawa saya ke jalur tertentu, dibandingkan dengan hanya memberitahu saya di mana setiap node individu dapat pergi. Saya kira cara termudah untuk menjelaskan kebingungan saya adalah dengan memberikan contoh:

Jadi misalnya, katakanlah saya memiliki grafik seperti ini:

masukkan deskripsi gambar di sini

Dan tujuan saya adalah beralih dari A ke E (semua sisi tidak berbobot).

Saya mulai dari A, karena itulah asal saya. Saya mengantri A, diikuti dengan segera mengeluarkan A dan menjelajahinya. Ini menghasilkan B dan D, karena A terhubung ke B dan D. Saya dengan demikian mengantri B dan D.

Saya dequeue B dan menjelajahinya, dan menemukan bahwa itu mengarah ke A (sudah dieksplorasi), dan C, jadi saya mengantri C. Saya kemudian dequeue D, dan menemukan bahwa itu mengarah ke E, tujuan saya. Saya kemudian dequeue C, dan menemukan bahwa itu juga mengarah ke E, tujuan saya.

Saya tahu secara logis bahwa jalur tercepat adalah A-> D-> E, tetapi saya tidak yakin bagaimana tepatnya pencarian pertama kali membantu - bagaimana saya harus merekam jalur sehingga ketika saya selesai, saya dapat menganalisis hasilnya dan melihat bahwa jalur terpendek adalah A-> D-> E?

Juga, perhatikan bahwa saya sebenarnya tidak menggunakan pohon, jadi tidak ada simpul "induk", hanya anak-anak.

Jake
sumber
2
"Juga, perhatikan bahwa saya menggunakan sebenarnya tidak menggunakan pohon, jadi tidak ada" orangtua "node, hanya anak-anak" - yah Anda jelas harus menyimpan orang tua di suatu tempat. Untuk DFS Anda melakukannya secara tidak langsung melalui tumpukan panggilan, untuk BFS Anda harus melakukannya secara eksplisit. Tidak ada yang dapat Anda lakukan tentang hal itu, saya khawatir :)
Voo

Jawaban:

85

Secara teknis, pencarian Breadth-first (BFS) dengan sendirinya tidak memungkinkan Anda menemukan jalur terpendek, hanya karena BFS tidak mencari jalur terpendek: BFS menggambarkan strategi untuk mencari grafik, tetapi tidak mengatakan bahwa Anda harus mencari apapun khususnya.

Algoritma Dijkstra mengadaptasi BFS untuk memungkinkan Anda menemukan jalur terpendek satu sumber.

Untuk mengambil jalur terpendek dari titik asal ke sebuah simpul, Anda perlu mempertahankan dua item untuk setiap simpul dalam grafik: jarak terpendeknya saat ini, dan simpul sebelumnya di jalur terpendek. Awalnya semua jarak diatur hingga tak terbatas, dan semua pendahulu diatur ke kosong. Dalam contoh Anda, Anda menetapkan jarak A ke nol, dan kemudian melanjutkan dengan BFS. Pada setiap langkah Anda memeriksa apakah Anda dapat meningkatkan jarak turunan, yaitu jarak dari titik asal ke pendahulunya ditambah panjang tepi yang Anda jelajahi kurang dari jarak terbaik saat ini untuk simpul yang dimaksud. Jika Anda dapat meningkatkan jarak, atur jalur terpendek baru, dan ingat pendahulunya melalui jalur mana yang telah diperoleh. Ketika antrian BFS kosong, pilih sebuah node (dalam contoh Anda, itu E) dan lintasi pendahulunya kembali ke asal.

Jika ini terdengar agak membingungkan, wikipedia memiliki bagian kode pseudocode yang bagus tentang topik ini.

dasblinkenlight
sumber
Terima kasih! Saya telah membaca pseudocode sebelumnya tetapi tidak dapat memahaminya, penjelasan Anda membuatnya klik untuk saya
Jake
46
Saya ingin membuat catatan berikut untuk orang-orang yang melihat posting ini di masa depan: Jika tepinya tidak berbobot, tidak perlu menyimpan "jarak terpendek saat ini" untuk setiap node. Semua yang perlu disimpan adalah induk untuk setiap node yang ditemukan. Dengan demikian, ketika Anda memeriksa sebuah simpul dan mem-enqueue semua penggantinya, cukup atur induk dari simpul-simpul tersebut ke simpul yang Anda periksa (ini akan berlipat ganda dengan menandainya "ditemukan"). Jika pointer orangtua ini adalah NUL / nil / Tidak Ada untuk setiap node yang diberikan, itu berarti bahwa belum ditemukan oleh BFS atau itu adalah simpul sumber / root itu sendiri.
Shashank
@Shashank Jika kita tidak menjaga jarak maka bagaimana kita tahu jarak terdekat, tolong jelaskan lebih lanjut.
Gaurav Sehgal
12
@gauravsehgal Komentar itu untuk grafik dengan tepi yang tidak berbobot. BFS akan menemukan jarak terpendek hanya karena pola pencarian radial yang mempertimbangkan node dalam urutan jaraknya dari titik awal.
Shashank
13
Kiat untuk pembaca komentar @ Shashank: tidak berbobot dan berbobot seragam (mis. Semua sisi berbobot = 5) adalah setara.
TWiStErRob
54

Seperti yang ditunjukkan di atas, BFS hanya dapat digunakan untuk menemukan jalur terpendek dalam grafik jika:

  1. Tidak ada loop

  2. Semua tepi memiliki bobot yang sama atau tidak sama berat.

Untuk menemukan jalur terpendek, yang harus Anda lakukan adalah mulai dari sumber dan melakukan pencarian pertama yang luas dan berhenti ketika Anda menemukan Node tujuan Anda. Satu-satunya hal tambahan yang perlu Anda lakukan adalah memiliki array sebelumnya [n] yang akan menyimpan node sebelumnya untuk setiap node yang dikunjungi. Sumber sebelumnya bisa nol.

Untuk mencetak path, loop sederhana melalui array [] sebelumnya dari sumber hingga Anda mencapai tujuan dan mencetak node. DFS juga dapat digunakan untuk menemukan jalur terpendek dalam grafik di bawah kondisi yang sama.

Namun, jika grafiknya lebih kompleks, mengandung tepi dan loop berbobot, maka kita memerlukan versi BFS yang lebih canggih, yaitu algoritma Dijkstra.

javaProgrammer
sumber
1
Dijkstra jika tidak -berat bobot gunakan bellman ford algo if
-veberat
Apakah BFS bekerja untuk menemukan semua jalur terpendek antara dua node?
Maria Ines Parnisari
35
@javaProgrammer, itu tidak benar. BFS dapat digunakan untuk menemukan jalur terpendek dalam grafik siklik tanpa bobot juga. Jika grafik tidak berbobot, maka BFS dapat diterapkan untuk SP tanpa memiliki loop.
Andrei Kaigorodov
3
To print the path, simple loop through the previous[] array from source till you reach destination.Tetapi sumber sebelumnya adalah nol. Saya pikir yang Anda maksud adalah backtrace from destination using the previous array until you reach the source,.
aandis
2
Mengapa Anda mengatakan DFS akan bekerja dalam kondisi serupa? Apakah tidak mungkin bagi DFS untuk mengambil rute bulat-naif untuk mendapatkan dari node start-> end, dan karena itu memberi Anda jalan yang bukan yang terpendek?
James Wierzba
26

Dari tutorial di sini

"Ini memiliki properti yang sangat berguna bahwa jika semua tepi dalam grafik tidak berbobot (atau bobot yang sama) maka pertama kali sebuah simpul dikunjungi adalah jalur terpendek ke simpul itu dari simpul sumber"

acheron55
sumber
Ini bagus untuk simpul yang dapat langsung dijangkau (1-> 2) (2 dicapai langsung dari 1). Untuk simpul yang tidak dapat dijangkau secara langsung ada lebih banyak pekerjaan (1-> 2-> 3, 3 tidak dapat dicapai langsung dari 1). Tentu saja, itu masih benar mengingat secara individual, yaitu 1-> 2 & 2-> 3 secara individual adalah jalur terpendek.
Manohar Reddy Poreddy
11

Saya telah menghabiskan 3 hari
akhirnya memecahkan pertanyaan grafik yang
digunakan untuk
menemukan jarak terpendek
menggunakan BFS

Ingin berbagi pengalaman.

When the (undirected for me) graph has
fixed distance (1, 6, etc.) for edges

#1
We can use BFS to find shortest path simply by traversing it
then, if required, multiply with fixed distance (1, 6, etc.)

#2
As noted above
with BFS
the very 1st time an adjacent node is reached, it is shortest path

#3
It does not matter what queue you use
   deque/queue(c++) or
   your own queue implementation (in c language)
   A circular queue is unnecessary

#4
Number of elements required for queue is N+1 at most, which I used
(dint check if N works)
here, N is V, number of vertices.

#5
Wikipedia BFS will work, and is sufficient.
    https://en.wikipedia.org/wiki/Breadth-first_search#Pseudocode

Saya telah kehilangan 3 hari mencoba semua alternatif di atas, memverifikasi & memverifikasi ulang lagi dan lagi di atas
mereka bukan masalah.
(Cobalah untuk menghabiskan waktu mencari masalah lain, jika Anda tidak menemukan masalah dengan di atas 5).


Penjelasan lebih lanjut dari komentar di bawah ini:

      A
     /  \
  B       C
 /\       /\
D  E     F  G

Asumsikan di atas adalah grafik
grafik Anda turun ke bawah
Untuk A, adjacents adalah B & C
Untuk B, adjacents adalah D & E
Untuk C, adjacents adalah F & G

katakanlah, mulai simpul adalah A

  1. ketika Anda mencapai A, ke, B & C jarak terdekat ke B & C dari A adalah 1

  2. ketika Anda mencapai D atau E, melalui B, jarak terdekat ke A & D adalah 2 (A-> B-> D)

sama, A-> E adalah 2 (A-> B-> E)

juga, A-> F & A-> G adalah 2

Jadi, sekarang alih-alih 1 jarak antar node, jika 6, maka gandakan jawabannya dengan 6
contoh,
jika jarak antara masing-masing adalah 1, maka A-> E adalah 2 (A-> B-> E = 1 + 1 )
jika jarak antara masing-masing adalah 6, maka A-> E adalah 12 (A-> B-> E = 6 + 6)

ya, bfs dapat mengambil jalur apa pun
tetapi kami menghitung untuk semua jalur

jika Anda harus beralih dari A ke Z, maka kami menempuh semua jalur dari A ke perantara I, dan karena akan ada banyak jalur, kami membuang semua kecuali jalur terpendek hingga saya, lalu melanjutkan dengan jalur terpendek ke depan ke simpul J
lagi jika ada beberapa jalur dari I ke J, kita hanya mengambil satu
contoh terpendek ,
asumsikan,
A -> I kita memiliki jarak 5
(LANGKAH) berasumsi, I -> J kita memiliki banyak jalur, dari jarak 7 & 8, karena 7 adalah yang terpendek
kita ambil A -> J sebagai 5 (A-> I terpendek) + 8 (terpendek sekarang) = 13
jadi A-> J sekarang 13
kita ulangi sekarang di atas (LANGKAH) untuk J -> K dan seterusnya, sampai kita dapatkan ke Z

Baca bagian ini, 2 atau 3 kali, dan menggambar di atas kertas, Anda pasti akan mendapatkan apa yang saya katakan, semoga beruntung


Manohar Reddy Poreddy
sumber
Bisakah Anda menjelaskan bagaimana Anda berhasil menemukan jalur terpendek dengan pencarian pertama yang luas. Pencarian pertama yang luas terutama mencari sebuah simpul, bisa ada n jalur ke simpul tujuan dari simpul sumber & bfs dapat mengambil jalur apa pun. Bagaimana Anda menentukan jalur terbaik?
underdog
saya telah menambahkan bagian 'penjelasan lebih lanjut' pada jawaban di atas, beri tahu saya jika itu memuaskan
Manohar Reddy Poreddy
1
Saya melihat Anda mencoba menjalankan BFS pada grafik tertimbang. Dari jarak 7 & 8 mengapa Anda memilih 8? kenapa tidak 7? bagaimana jika 8 node tidak memiliki tepi lebih jauh ke tujuan? Aliran harus memilih 7 lalu.
underdog
pertanyaan bagus, terbalik, ya, kami tidak membuang, kami melacak semua node yang berdekatan, sampai kami mencapai tujuan. BFS hanya akan bekerja ketika hanya ada jarak konstan seperti semua 7 atau semua 8. Saya memberikan satu generik yang memiliki 7 & 8 yang juga disebut sebagai algoritma dijkstra.
Manohar Reddy Poreddy
maaf, tidak yakin apa yang Anda maksud, lihat en.wikipedia.org/wiki/Dijkstra's_algorithm
Manohar Reddy Poreddy
2

Berdasarkan jawaban acheron55 saya memposting implementasi yang mungkin di sini .
Berikut ini ringkasan singkatnya:

Yang harus Anda lakukan adalah melacak jalur yang dilaluinya target telah tercapai. Cara sederhana untuk melakukannya, adalah mendorong ke Queueseluruh jalur yang digunakan untuk mencapai suatu simpul, bukan dari simpul itu sendiri.
Manfaat melakukannya adalah ketika target telah tercapai, antrian memegang jalur yang digunakan untuk mencapainya.
Ini juga berlaku untuk grafik siklik, di mana simpul dapat memiliki lebih dari satu orangtua.

lebih tenang
sumber
0

Mengunjungi utas ini setelah beberapa saat tidak aktif, tetapi mengingat bahwa saya tidak melihat jawaban yang menyeluruh, inilah dua sen saya.

Pencarian Breadth-first akan selalu menemukan jalur terpendek dalam grafik tanpa bobot. Grafik dapat berupa siklik atau asiklik.

Lihat di bawah untuk kodesemu. Kodesemu ini mengasumsikan bahwa Anda menggunakan antrian untuk mengimplementasikan BFS. Itu juga mengasumsikan Anda dapat menandai simpul sebagai dikunjungi, dan bahwa setiap simpul menyimpan parameter jarak, yang diinisialisasi hingga tak terbatas.

mark all vertices as unvisited
set the distance value of all vertices to infinity
set the distance value of the start vertex to 0
push the start vertex on the queue
while(queue is not empty)   
    dequeue one vertex (well call it x) off of the queue
    if the value of x is the value of the end vertex: 
        return the distance value of x
    otherwise, if x is not marked as visited:
        mark it as visited
        for all of the unmarked children of x:
            set their distance values to be the distance of x + 1
            enqueue them to the queue
if here: there is no path connecting the vertices

Perhatikan bahwa pendekatan ini tidak berfungsi untuk grafik berbobot - untuk itu, lihat algoritma Dijkstra.

Matthew Russell
sumber
-6

Solusi berikut ini berfungsi untuk semua kasus uji.

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

   public static void main(String[] args)
        {
            Scanner sc = new Scanner(System.in);

            int testCases = sc.nextInt();

            for (int i = 0; i < testCases; i++)
            {
                int totalNodes = sc.nextInt();
                int totalEdges = sc.nextInt();

                Map<Integer, List<Integer>> adjacencyList = new HashMap<Integer, List<Integer>>();

                for (int j = 0; j < totalEdges; j++)
                {
                    int src = sc.nextInt();
                    int dest = sc.nextInt();

                    if (adjacencyList.get(src) == null)
                    {
                        List<Integer> neighbours = new ArrayList<Integer>();
                        neighbours.add(dest);
                        adjacencyList.put(src, neighbours);
                    } else
                    {
                        List<Integer> neighbours = adjacencyList.get(src);
                        neighbours.add(dest);
                        adjacencyList.put(src, neighbours);
                    }


                    if (adjacencyList.get(dest) == null)
                    {
                        List<Integer> neighbours = new ArrayList<Integer>();
                        neighbours.add(src);
                        adjacencyList.put(dest, neighbours);
                    } else
                    {
                        List<Integer> neighbours = adjacencyList.get(dest);
                        neighbours.add(src);
                        adjacencyList.put(dest, neighbours);
                    }
                }

                int start = sc.nextInt();

                Queue<Integer> queue = new LinkedList<>();

                queue.add(start);

                int[] costs = new int[totalNodes + 1];

                Arrays.fill(costs, 0);

                costs[start] = 0;

                Map<String, Integer> visited = new HashMap<String, Integer>();

                while (!queue.isEmpty())
                {
                    int node = queue.remove();

                    if(visited.get(node +"") != null)
                    {
                        continue;
                    }

                    visited.put(node + "", 1);

                    int nodeCost = costs[node];

                    List<Integer> children = adjacencyList.get(node);

                    if (children != null)
                    {
                        for (Integer child : children)
                        {
                            int total = nodeCost + 6;
                            String key = child + "";

                            if (visited.get(key) == null)
                            {
                                queue.add(child);

                                if (costs[child] == 0)
                                {
                                    costs[child] = total;
                                } else if (costs[child] > total)
                                {
                                    costs[child] = total;
                                }
                            }
                        }
                    }
                }

                for (int k = 1; k <= totalNodes; k++)
                {
                    if (k == start)
                    {
                        continue;
                    }

                    System.out.print(costs[k] == 0 ? -1 : costs[k]);
                    System.out.print(" ");
                }
                System.out.println();
            }
        }
}
pengguna3819236
sumber
4
Diturunkan karena tidak menjawab pertanyaan. Cukup menempelkan cuplikan kode tidak akan berfungsi di SO.
Rishabh Agrahari