Pytania otagowane jako shortest-path

Pytania o algorytmiczne problemy znalezienia najkrótszych ścieżek między węzłami na grafie.

3
Jakie jest znaczenie „szerokość” przy pierwszym wyszukiwaniu?
Uczyłem się o pierwszym wyszukiwaniu szerokości i przyszło mi do głowy pytanie, dlaczego tak nazywa się BFS. W książce Wprowadzenie do algorytmów CLRS przeczytałem następujący powód: Poszukiwanie szerokości jest tak nazwane, ponieważ równomiernie rozszerza granicę między odkrytymi i nieodkrytymi wierzchołkami na całej szerokości granicy. Nie jestem jednak w stanie zrozumieć …
1
Czy potrafimy znaleźć k najkrótszych ścieżek między wszystkimi parami szybciej niż wielokrotne rozwiązywanie problemu parami?
Chcę produkować kkk najkrótsza droga (kkkbyłoby mniej niż 10) między wszystkimi parami na wykresie. Wykres to (właściwie mapa metra): dodatnio ważony bezkierunkowy rzadki z około 100 węzłami Mój obecny plan ma zastosowanie kkknajkrótsza ścieżka trasy do każdej pary; Teraz szukam bardziej wydajnej alternatywy (prawdopodobnie z programowaniem dynamicznym).
1
Znalezienie najkrótszej ścieżki między dwoma węzłami
Biorąc pod uwagę ważony digraf G=V,EG=V,EG=V,Ei funkcja wagi, d(u,v)d(u,v)d(u,v), zwykle można użyć algorytmu Dijkstry, aby uzyskać najkrótszą ścieżkę. Interesuje mnie to, jak uzyskać2nd2nd2^{nd}- najkrótsza ścieżka, 3rd3rd3^{rd}-krótko i tak dalej. Pytania: Czy istnieje skuteczny algorytm do uzyskania i-tej najkrótszej ścieżki między dwoma węzłami na wykresie ważonym? Czy istnieje skuteczny algorytm pozwalający …
3
Unikalna ścieżka na ukierunkowanym wykresie
Projektuję algorytm dla klasy, który określi, czy skierowany wykres jest unikalny w odniesieniu do wierzchołka vvv tak, że dla każdego u ≠ vu≠vu \ne v jest co najwyżej jedna ścieżka z vvv do uuu. Zacząłem od użycia BFS (wyszukiwanie szerokości), aby znaleźć najkrótszą ścieżkę od v do innego wierzchołka u, …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.