Gdy Grono miało stosunkowo niewielu użytkowników opracowany został program, który obliczał najkrótszą ścieżkę pomiędzy dwoma osobami. Była to implementacja standardowego algorytmu Dijkstry.

W miarę gdy Grono się rozwijało i rosła liczba jego użytkowników, metoda ta przestała działać wystarczająco szybko. Czas wyszukiwania ścieżek sięgał kilku sekund. Postanowiliśmy to zmienić.

Próba pierwsza: metoda Dijkstry
Algorytm Dijkstry służy do znajdowania najkrótszych połączeń w grafach. W naszym przypadku użytkowników można rozpatrywać jako węzły, a połączenia pomiędzy użytkownikami jako krawędzie grafu. Jednak zauważmy, że struktura grafu sieci społecznej jest specyficzna. Każde podanie ręki, każda krawędź grafu, ma jednakową wartość, a odległość pomiędzy dowolnymi użytkownikami (węzłami) jest zawsze krótka i wynosi co najwyżej kilkanaście podań ręki.

Dzięki tym cechom możemy zawęzić metodę Dijkstry do naszych potrzeb. Złożoność standardowego algorytmu Dijsktry, O(V * log(V) + E), dla naszego przypadku można zmniejszyć do postaci O(V+E). Osiągniemy to implementując kolejkę priorytetową w algorytmie Dijkstry jako tablicę haszującą. Dzięki temu wszystkie niezbędne operacje, takie jak usuwanie węzłów, zmienianie ich wag i wyszukiwanie węzła o najmniejszej wadze, można wykonać w czasie stałym (w przeciwieństwie do standardowej implementacji metody Dijkstry, gdzie jest to czas logarytmiczny).

Próba druga: szybko zakończyć obliczenia
Standardowy algorytm Dijkstry oblicza ścieżkę od węzła początkowego do wszystkich węzłów w grafie. Odnosząc to do naszego problemu, gdy szukamy drogi od gronowicza A do B, to komputer oblicza najkrótsze ścieżki od gronowicza A do wszystkich osób w Gronie. Aczkolwiek jako rezultat używana jest zaledwie jedna wyliczona droga. Rozsądne wydaje się przerwanie obliczeń po znalezieniu pierwszej odpowiadającej ścieżki. Można by się spodziewać, że w ten sposób znacznie poprawimy wydajność, gdyż nie będziemy wykonywali wielu niepotrzebnych obliczeń.

Niestety w praktyce poprawa wydajności okazała się niewielka. Dzieje się tak dlatego, że rozkład znajomości w gronie jest bardzo specyficzny. Liczba znajomych w kolejnych podaniach ręki wzrasta tak szybko, że w odległości 4 podań ręki od użytkownika znajdują się już praktycznie wszyscy. Tak więc w momencie w którym przerywalibyśmy szukanie, okazuje się że i tak przeszukaliśmy już większość możliwych dróg.

Oto przykładowe dane, pokazujące jak szybko rośnie liczba znajomych w kolejnych odległościach od pewnego użytkownika:

Odległość Liczba    Liczba
          Węzłów   Krawędzi
#00  |        1n       59e
#01  |       59n     4917e
#02  |     3654n   463608e
#03  |   159042n 17669289e
#04  |   557105n 25225499e
#05  |   261623n   564312e
#06  |    25225n    28748e
#07  |     1879n     2104e
#08  |      190n      221e
#09  |       29n       33e
#10  |        4n        6e
#11  |        2n        2e

Próba trzecia: liczymy z obu stron
Kolejną specyficzną cechą Grona jest fakt, że jeżeli ktoś jest moim znajomym, to ja muszę być również jego znajomym. Możemy powiedzieć, że graf znajomości nie jest skierowany. Wynika z tego, że jeśli odwrócimy ścieżkę od użytkownika A do B, to będzie ona poprawną ścieżką od B do A.

Jak już wspomniałem wcześniej, im dalszy poziom znajomości obliczamy, tym więcej danych musimy obrabiać. Załóżmy, że użytkownika A dzielą cztery podania ręki do użytkownika B. Nie musimy liczyć kosztownego czwartego poziomu znajomości od użytkownika A i w wynikach szukać B. Możemy policzyć wszystkie węzły w odległości 2 od A, wszystkie węzły w odległości 2 od B, a następnie porównać wyniki. Jeśli jakiś użytkownik jest w odległości 2 od A, i zarazem jest w odległości 2 od B, to znaczy że przez niego przebiega szukana ścieżka pomiędzy A i B.

Stosując tą metodę jesteśmy w stanie znacznie zmniejszyć obliczania, gdyż nie musimy obrabiać danych w odległości 3 i więcej od węzła A.

Próba czwarta
Wyniki opisanej metody są bardzo dobre. Jednak w pewnych przypadkach obliczenia w dalszym ciągu trwały długo.

Powyższa metoda wykonuje po jednym kroku algorytmu od węzła A i od węzła B, a następnie porównuje wyniki. Zamiast wykonywać po jednym kroku z obu stron, należy tak zmodyfikować program, aby wykonywał obliczenia tylko po tej stronie ścieżki, po której mamy mniej węzłów. Dzięki temu mamy pewność, że wykonujemy możliwie mało obliczeń. Niestety, odbywa się to kosztem dwukrotnie większej liczby scaleń rezultatów obliczeń.

Podsumowanie
Po uwzględnieniu specyficznych cech struktury Grona, udało się znacznie zmodyfikować algorytm Dijkstry. Dzięki temu czas wyszukiwania najkrótszych ścieżek pomiędzy Gronowiczami spadł z kilku sekund do kilku milisekund.

Jaka jest złożoność przedstawionej metody? (autor: Adam Kolipiński, plazmonik (małpa) gmail.com)

TWIERDZENIE: Weźmy G: graf nieskierowany, o wagach krawędzi równych 1, o nieskończonej liczbie wierzchołków, spójny, taki, że odległość między dowolnymi wierzchołkami jest skończona, oraz taki, że z każdego wierzchołka wychodzi co najwyżej K krawędzi. Załóżmy że odległość między wierzchołkami A i B wynosi N.

Pesymistyczny koszt algorytmu Dijktry wynosi O(K^N ), a koszt algorytmu liczącego z dwóch stron: O(K^N/2) + koszt scalania tablic.

DOWÓD: Algorytm Dijkstry potrzebuje zbadać K wierzchołków aby dojść do wierzchołka o odległości 1, K² wierzchołków, aby dojść do wierzchołka o odległości 2, itd, przy założeniu najgorszego przypadku, a więc za każdym razem trafiamy na nieodwiedzony wcześniej wierzchołek.

To daje nam sumę ciągu geometrycznego:

K(Dijk) = k¹ + k² + .... + kⁿ = (1-kⁿ)/(1-k) ~ kⁿ

Algorytm liczący z dwóch stron bada 2K wierzchołków aby dojść do wierzchołka o odległości 1 i 2, 2K², aby dojść do wierzchołka o odległości 3 i 4, itd. co daje sumę:

K(DStron) = 2 * (k¹ + k² + ... + k ^n/2) + n = 2 * (1 – k^n/2)/(1 – k) + n ~ k^n/2

Przy każdym kroku algorytmu trzeba scalić tablicę, stąd to ‘+n’.