Złożoność czasowa znalezienia średnicy wykresu

Jaka jest złożoność czasowa znalezienia średnicy wykresu ?$G=(V,E)$

• ${O}(|V|^2)$
• ${O}(|V|^2+|V| \cdot |E|)$
• ${O}(|V|^2\cdot |E|)$
• ${O}(|V|\cdot |E|^2)$

Średnica wykresu $G$ jest maksymalnym zbiorem najkrótszych odległości ścieżki między wszystkimi parami wierzchołków na wykresie.

Nie mam pojęcia, co z tym zrobić, potrzebuję pełnej analizy, jak rozwiązać taki problem.

Aktualizacja:

To rozwiązanie jest nieprawidłowe.

Rozwiązanie jest niestety prawdziwe (i proste) dla drzew! Znalezienie średnicy drzewa nawet tego nie potrzebuje. Oto kontrprzykład dla wykresów (średnica wynosi 4, algorytm zwraca 3, jeśli wybierzesz to ):$v$

Jeśli wykres jest skierowany, jest to dość skomplikowane, oto część papieru, która twierdzi, że wyniki w gęstym przypadku są szybsze niż stosowanie algorytmów dla najkrótszych ścieżek wszystkich par.

Jednak moja główna uwaga dotyczy przypadku, w którym wykres nie jest skierowany, a przy wagach nieujemnych kilkakrotnie słyszałem o fajnej sztuczce:

1. Wybierz wierzchołek$v$
2. Znajdź tak, że jest maksymalned ( v , u $u$$d(v,u)$
3. Znajdź tak, że jest maksymalned ( u , w $w$$d(u,w)$
4. Zwróć$d(u,w)$

Jego złożoność jest taka sama, jak dwa kolejne pierwsze wyszukiwania¹, tzn. jeśli wykres jest połączony².$O(|E|)$

Wydawało się to folklorem, ale w tej chwili wciąż staram się zdobyć referencję lub udowodnić jej poprawienie. Zaktualizuję, kiedy osiągnę jeden z tych celów. Wydaje się to takie proste, że teraz zamieszczam swoją odpowiedź, być może ktoś dostanie ją szybciej.

¹ jeśli wykres jest ważony, wikipedia wydaje się mówić ale jestem pewien co do .O ( | E | log | V |$O(|E|+|V|\log|V|)$$O(|E|\log|V|)$

² Jeśli wykres nie jest połączony, otrzymujesz ale może być konieczne dodanie aby wybrać jeden element z każdego podłączonego komponentu. Nie jestem pewien, czy jest to konieczne, a mimo to możesz zdecydować, że średnica jest w tym przypadku nieskończona.$O(|V|+|E|)$$O(α(|V|))$

Zakładam, że masz na myśli średnicę od , który jest najdłuższy najkrótsza ścieżka znaleźć w .$G$$G$

Znalezienie średnicy można wykonać, znajdując najpierw wszystkie najkrótsze ścieżki i określając maksymalną znalezioną długość. Algorytm Floyda-Warshalla robi to w czasie . Algorytm Johnsona można zaimplementować, aby osiągnąć czas.O ( | V | 2 log | V | + | V | ⋅ | E |$\Theta(|V|^3)$$\cal{O}(|V|^2\log |V| + |V|\cdot|E|)$

Wydaje się, że trudniejszy do osiągnięcia jest mniejszy limit czasu działania w najgorszym przypadku, ponieważ istnieją odległości do rozważenia i obliczenia tej odległości w podliniowym (zamortyzowanym) czasie każdy będzie trudny; zobacz tutaj powiązane powiązanie. Zwróć uwagę na ten artykuł, który stosuje inne podejście i uzyskuje (nieco) szybszy algorytm.$\cal{O}(|V|^2)$

Można również rozważyć teoretyczne podejście do grafu algebraicznego. Średnica jest najmniejsza liczba całkowita ul matrycy ma tę właściwość, że wszystkie wpisy są niezerowe. Możesz znaleźć według iteracji mnożenia macierzy. Algorytm średnicy wymaga wtedy czasu , gdzie jest granicą mnożenia macierzy. Na przykład, przy uogólnieniu algorytmu Coppersmith-Winograd przez Vassilevska Williams, algorytm średnicy działałby w . Krótkie wprowadzenie znajduje się w rozdziale 3 w książce Fan Chung tutaj .$\text{diam}(G)$$t$$M=I+A$$M^t$$t$$O(\log n)$$O(M(n) \log n)$$M(n)$$O(n^{2.3727} \log n)$

Jeśli ograniczysz swoją uwagę do odpowiedniej klasy grafu, możesz rozwiązać problem APSP w optymalnym czasie . Te klasy obejmują co najmniej wykresy interwałowe, wykresy łuków kołowych, wykresy permutacji, dwustronne wykresy permutacji, wykresy silnie akordowe, wykresy akordowe dwuczęściowe, wykresy dziedziczne odległości i wykresy podwójnie akordowe. Na przykład patrz Dragan, FF (2005). Szacowanie wszystkich par najkrótszych ścieżek w ograniczonych rodzinach grafów: ujednolicone podejście. Journal of Algorytmy, 57 (1), 1-21 i odnośniki tam zawarte.$O(n^2)$

Założenia:
1. Wykres jest nieważony
2. Wykres jest skierowany

Złożoność czasowa O (| V || E |).

Algorytm:

ComputeDiameter(G(V,E)):
  if ( isCycle( G(v,E) ) ) then
     return INFINITY
  if ( not isConnected( G(V,E) )) then
     return INFINITY
  diameter = 0
  for each vertex u in G(V,E):
     temp = BFS(G,u)
     diameter = max( temp , diameter )
  return diameter

Objaśnienie:
Sprawdzamy cykl. jeśli wykres zawiera cykl, poruszamy się w pętli, więc będziemy mieli nieskończoną odległość. Sprawdzamy połączenie. Jeśli wykres nie jest połączony, oznacza to wierzchołek u od G1 do wierzchołka v w G2. Gdzie G1 i G2 to dowolne dwa podgrupy, które nie są połączone. Więc znów będziemy mieć nieskończony dystans. Użyjemy BFS do obliczenia maksymalnej odległości między danym węzłem (u) do wszystkich innych węzłów (v), które są osiągalne z u. Następnie weźmiemy maksimum poprzednio obliczonej średnicy i wynik zwrócony przez BFS. Będziemy mieć aktualną maksymalną średnicę.

Analiza czasu pracy:

1. O (| E |) przy użyciu DFS
2. O (| E |) przy użyciu DFS
3. BFS działa w czasie O (| E |).
4. Musimy wywołać funkcję BFS dla każdego wierzchołka, więc suma zajmie czas O (| V || E |).

Czas całkowity = O (| v || E |) + O (| E |) + O (| E |)
Ponieważ | V || E | > | E |
więc mamy czas działania jako O (| v || E |).

BFS
DFS

Uwaga: To nie jest eleganckie rozwiązanie tego problemu.