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

27

Jaka jest złożoność czasowa znalezienia średnicy wykresu ?sol=(V.,mi)

  • O(|V.|2))
  • O(|V.|2)+|V.||mi|)
  • O(|V.|2)|mi|)
  • O(|V.||mi|2))

Średnica wykresu sol 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.

Gigili
źródło
4
Proszę opracować odrobinę. Dlaczego ten problem Cię interesuje? Potrzebujesz podpowiedzi, pełnej analizy lub referencji? Czy jesteś zainteresowany czasem najgorszym lub średnim? Czy sol skierowany?
Raphael
@Raphael: Oczywiście nie potrzebuję podpowiedzi, potrzebuję pełnej analizy. Zresztą i tak zredagowałem swoje pytanie.
Gigili,
1
@Gigili Masz na myśli Θ we wszystkich przypadkach, prawda? W przeciwnym razie wszystkie są uwzględniane przez ostatnią możliwość (która jest na ogólnych wykresach równa O(|V.|5) ), co czyni ją poprawną odpowiedzią, zakładając, że co najmniej jedna odpowiedź ma być poprawna. Dodatkowym problemem jest to, że na wykresie z cyklami nie ma najdłuższej ścieżki. Co oznacza „najdłuższy dystans”?
Raphael
@Gigili Skąd pochodzą cztery opcje?
uli

Odpowiedzi:

5

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

wprowadź opis zdjęcia tutaj


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łekv
  2. Znajdź tak, że jest maksymalned ( v , u )ud(v,u)
  3. Znajdź tak, że jest maksymalned ( u , w )wd(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|))

jmad
źródło
Aby zmusić Dijsktrę do pracy w określonym czasie, musisz użyć hałd Fibonacciego, a nie zwykłej implementacji.
Suresh,
8
To zdecydowanie błędna odpowiedź, ten algorytm to folklor, ale na drzewach nie są to ogólne wykresy. PS: Widzę twój licznik, ale oznaczenie odpowiedzi jako złej nie jest dobrą odpowiedzią.
Mam dwa pytania dotyczące niewłaściwego rozwiązania. 1. Czy dałoby to przynajmniej zakres, w którym musi znajdować się poprawna odpowiedź? np. jeśli metoda znajdzie średnicę d , czy poprawne rozwiązanie będzie między d a 2d ? 2. Co się stanie, jeśli dodamy kolejną pośrednią i rozważymy wszystkie węzły znalezione przez pośrednią (nie tylko jedną)? Przeciwny przykład podany w poście działałby wtedy, ponieważ prawdziwe wierzchołki peryferyjne znajdują się wśród węzłów znalezionych przez drugą pośrednią.
mafu
32

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

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 | )Θ(|V|3)O(|V|2log|V|+|V||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.O(|V|2)

Raphael
źródło
2
Jeśli dostaniesz zapłatę na tych dokumentach, sprawdź Google Scholar.
Raphael
Warto również zauważyć ten wyjątek w przypadku drzew bezkierunkowych , w których można uzyskać średnicę. za pomocą tylko jednego przejścia dfs.
azam
15

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 .diam(G)tM=I+AMttO(logn)O(M(n)logn)M(n)O(n2.3727logn)

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(n2)

Juho
źródło
2
Warto zauważyć, że ten algorytm działa tylko w przypadku nieważonym.
GMB,
-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.

sonus21
źródło
Acykliczne połączone wykresy to drzewa, dla których problem jest łatwiejszy (ponieważ średnicę podaje się wtedy przez najdłuższą ścieżkę). Zostało to omówione tu i tutaj , gdzie podano szybsze algorytmy. (Jedno rekurencyjne przejście lub, alternatywnie, dwa BFS są wystarczające.)
Raphael
1
@Raphael Nie, acykliczne niekierowane wykresy to drzewa. DAG to DAG.
David Richerby,
@DavidRicherby Right. (Chociaż, technicznie rzecz biorąc, odpowiedź nie mówi, czy wyklucza cykle kierowane lub niekierowane.;)) W każdym razie, jest to nic innego jak rozwiązanie APSPP (podejście naiwne), które zostało już ujęte w ogólnym przypadku w poprzednich odpowiedziach.
Raphael
@Raphael Czy jesteś pewien, że wykresy acykliczne to drzewa? Wykres jest acykliczny nie oznacza, że ​​wykres będzie zawsze drzewem. Drzewo jest tego szczególnym przypadkiem. Jest to również prosty algorytm, a złożoność czasowa wynosi O (| V || E |).
sonus21,
Tak, jestem pewny. (Może myślisz o zakorzenionych drzewach, które mają inny smak.)
Raphael