Bellman ford kolejka podejście oparte od Sedgewick i Wayne - algorytmy, 4. wydanie

Question

studiowałem queue-based podejście do Bellman-Ford algorithm dla pojedynczego źródła najkrótszej ścieżki od Robert Sedgewick and Kevin Wayne - Algorithms, 4th edition kodu źródłowego dla algorytmu z książki jest obecna pod tym linkiem http://algs4.cs.princeton.edu/44sp/BellmanFordSP.java.

Mam dwa punkty jeden jest wątpliwości, a inne sugestie poprawy kodu.

1. W powyższym podejściu jest kod metody relaksacji dla relaksującej odległości od wierzchołków.

   for (DirectedEdge e : G.adj(v)) { 
       int w = e.to(); 
       if (distTo[w] > distTo[v] + e.weight()) { 
        distTo[w] = distTo[v] + e.weight(); 
        edgeTo[w] = e; 
        if (!onQueue[w]) { 
         queue.enqueue(w); 
         onQueue[w] = true; 
        } 
       } 
       if (cost++ % G.V() == 0){ 
        findNegativeCycle(); 
       } 
   } 
   

W ten sposób pod warunkiem, jest stosowany przed znalezieniem negatywny cyklu.

if (cost++ % G.V() == 0){ 
    findNegativeCycle(); 
} 

Przede są podzielenie kosztów przez liczbę vertices w wykres, aby sprawdzić negative cycle. Może to być spowodowane tym, że relaksacja odbywa się razy i jeśli czas relaksacji dla Vth czas oznacza, że ​​ma cykl, gdzie V jest liczbą wierzchołków.

Ale myślę, że w podejściu opartym na kolejce używają dzielnika do sprawdzania w regularnych odstępach czasu, jeśli wystąpił cykl, czy nie. Cykl może wystąpić przed lub tuż po powyższym warunku jest prawdziwy. Jeśli cykl wystąpił po spełnieniu powyższego warunku, to algorytm musi czekać do następnego warunku czasowego, aby był prawdziwy, aby wykryć cykl. Nie jest konieczne, aby cykl wystąpił dokładnie wtedy, gdy (cost++ % G.V() == 0) jest prawdziwy. Myślę więc, że dzielnik może być dowolną liczbą wystarczająco małą, abyśmy mogli sprawdzić cykl po odpowiednim czasie. Czy mam rację?

1. Kod poprawa sugestia jest findNegativeCycle() metoda może być zastosowana, aby powrócić prawdziwe w przypadku wystąpienia cyklu. A zatem. to condition-

   if (cost++ % G.V() == 0) { findNegativeCycle(); }

Może być zmieniane To-

if (cost++ % G.V() == 0) 
    if(findNegativeCycle()){ 
     return; 
    } 

W kodzie pętli utrzymuje się na prowadzeniu nawet jeśli findNegativeCycle() metoda znalazła cykl. Możemy więc wrócić, jeśli wystąpił cykl zamiast przetwarzania reszty pętli for.

Podziel się swoimi przemyśleniami na temat powyżej 2 punktów. Z góry dzięki.

Answer 1

1. Masz rację. W ich online materials, autorzy wyjaśniają, że sprawdzają każdą rozmowę V, aby amortyzować koszty budowy związane krawędzi ważony digraf i znalezienie cykl w nim:

związku z tym, aby realizować negativeCycle() BellmanFordSP. java buduje dwuwymiarowy digraf znakowany krawędziowo od krawędzi w edgeTo [] i szuka cyklu w tym digrafelu. Aby znaleźć cykl, używa on EdgeWeightedDirectedCycle.java, wersji DirectedCycle.java z Sekcja 4.3, przystosowany do pracy przy dwuznakach o krawędziach. Zamortyzujemy koszt tego czeku, wykonując tę ​​kontrolę tylko po każdej rozmowie telefonicznej V- , aby się zrelaksować().

Innymi słowy, możesz sprawdzać częściej, ale wtedy ryzykujesz utratą wydajności.

2. Znów masz rację. Istnienie ujemnego cyklu jest obecnie sprawdzane w pętli while w konstruktorze. Jednak w najgorszym przypadku metoda relax może wykryć cykl poprzez sprawdzenie pierwszej krawędzi w pętli for i zamiast wyjść, będzie kontynuować i sprawdzić inne krawędzie (maks. V-2). Dzięki proponowanej poprawie możesz zaoszczędzić znaczną ilość czasu.

Answer 2

Bardzo miło widzieć odpowiedzi Miljena Mikica. To naprawdę pomaga zrozumieć algorytm. Jednak wciąż mam inne pytanie. W tekście mówi: "Aby zakończyć implementację, musimy upewnić się, że algorytm kończy się po przejściu V. Jeden ze sposobów osiągnięcia tego celu to jawne śledzenie przebiegów." Tutaj wierzę, że zmienna „koszt” jest liczba przełęcze, ale nie powinny linie

if (cost++ % G.V() == 0) 
    findNegativeCycle(); 

być przynajmniej na zewnątrz pętli for? Jak

private void relax(EdgeWeightedDigraph G, int v) 
    { 
     for (DirectedEdge e : G.adj(v) 
      { 
        int w = e.to(); 
        if (distTo[w] > distTo[v] + e.weight()) 
         { 
          distTo[w] = distTo[v] + e.weight(); 
          edgeTo[w] = e; 
          if (!onQ[w]) 
           { 
             q.enqueue(w); 
             onQ[w] = true; 
           } 
         } 
       } 
     if (cost++ % G.V() == 0) 
       findNegativeCycle(); 
     } 

Właściwie nawet to poza pętli for, to nie najlepsze rozwiązanie, ponieważ podczas każdego przejścia, nie może być wiele wierzchołki zostać złagodzone. Dzięki temu można lepiej zaprojektować konstruktor BellmanFordSP, pamiętając, ile wierzchołków należy rozluźnić podczas każdego przejścia. Mam rację? Dzięki!