Dynamiczne aktualizowanie najkrótszych ścieżek

Question

Mam wykres, na którym często potrzebuję znać wszystkie najkrótsze ścieżki (lub raczej ich długości). Ponieważ nie chcę ich ponownie obliczać, przechowuję je w prostej tablicy i po prostu je od nich ściągam. Ponieważ wykres może się również zmieniać z biegiem czasu, będę musiał je ponownie obliczyć w wyznaczonym czasie.

Teraz następujące zmiany mogą się zdarzyć:

• Dodanie węzłem i krawędziowej do wykresu

• Zmiana długości krawędzi

• Dodanie nowej krawędzi wykresu

• Usuwanie krawędzi lub usuwanie węzła

We wszystkich przypadkach wszystkie węzły będą zawsze połączone, a wszystkie krawędzie mają dodatnie masy. Również wykres jest nieukierunkowany. Sekwencja operacji jest taka, że ​​wszystkie węzły zawsze będą pochodziły z tego samego komponentu wykresu. Jeśli węzeł lub krawędź zostanie usunięty przed dodaniem innych węzłów i krawędzi, wykres nie zostanie rozdzielony.

Na razie planuję po prostu robić aktualizacje, a następnie propagować wszystkie zmiany poprzez strukturę wykresu. Jednak nie jestem jeszcze pewien, jak poprawnie to znieść. W jaki sposób próbowałbyś osiągnąć te aktualizacje pamięci podręcznej?

EDIT:

Jak niektórzy z was zauważył to może być niezbędna do przeliczyć wszystko, gdy węzeł jest dodawany lub link zostanie zmieniony. Może to być na przykład, gdy wszystkie odległości zmieniają się poprzez aktualizację. Jeśli jednak po prostu propaguję zmiany za pomocą wykresu i relaksuję się podobnie do sposobu, w jaki jest to wykonywane dijkstras, być może będę musiał wielokrotnie odprężyć ten sam węzeł, ponieważ może nie wybrać optymalnej kolejności. Pytanie brzmi, jak zamówić kroki relaksacyjne, więc unikam wielu aktualizacji tak dobrze, jak to możliwe.

Nie jestem pewien, czy to ma sens, bez faktycznego pomysłu, który mam na myśli, ale mam nadzieję, że to wyjaśnia więcej.

Answer 1

Numer D* family of search algorithms dotyczy aktualizacji krótkich ścieżek w dynamicznie zmieniających się wykresach. Algorytmy zostały opracowane dla problemów związanych z planowaniem ścieżek robotów mobilnych. Chociaż algorytmy zwracają tylko najkrótszą ścieżkę od celu do aktualnej lokalizacji robota, możliwe, że będziesz w stanie również użyć swoich reguł księgowania i aktualizacji dla najkrótszych ścieżek.

Answer 2

Możesz obsłużyć przypadek, w którym usuwasz krawędź/węzeł dość łatwo. Po prostu śledź rzeczywistą ścieżkę między węzłami. Następnie, po usunięciu krawędzi/węzła, przejdź przez ścieżki i zobacz, na które zmiany wpływają. Ponownie oblicz najkrótsze ścieżki dla nich.

W przypadku, gdy zwiększasz wagę krawędzi, możesz użyć tej samej techniki.

Inne sprawy są znacznie trudniejsze do rozwiązania. Nie znam żadnej struktury algorytmów/danych, która przyspieszyłaby rekomputację.