Czy algorytm Dijkstry jest odpowiednim rozwiązaniem tego problemu z routingiem sygnałów?

Jestem w trakcie opracowywania modułu zarządzania i routingu sygnałów dla zintegrowanego systemu audiowizualnego i projektuję go z myślą o jak największej elastyczności w różnych sieciach dystrybucji sygnału. Celem tego modułu jest obsługa routingu w szeregu przełączników macierzowych ¹ i obsługa niezbędnej konwersji formatu.

Najlepszym rozwiązaniem, które zbadałem w tym momencie, jest odwzorowanie sieci na wykres z dyskretnymi wierzchołkami dla każdego typu sygnału obsługiwanego przez przełączniki, a następnie łączone za pomocą węzłów reprezentujących procesory wideo obsługujące konwersję formatu.

Kolory reprezentują formaty sygnałów. Okrągłe węzły to przełączniki, źródła lub ujścia. Węzły kwadratowe to procesory wideo, które wykonują konwersję formatu.

Stamtąd mogę użyć implementacji algorytmu Dijkstry, aby zidentyfikować ścieżkę, która musi zostać utworzona, aby uzyskać wejście X do wyjścia Y. Powinno to pozwolić na przekazanie danych o konfiguracji wejścia / wyjścia wszystkich przełączników i procesorów. i moduł odpowiednio się dostosuje.

Czy jest to właściwe rozwiązanie, czy istnieje alternatywne podejście, które może być warte zbadania?

_{¹ aka „przełącznik poprzeczny”, router wideo z wejściem M x wyjściami N, który obsługuje połączenia jeden do wielu. Każde urządzenie fizyczne może obsługiwać wiele formatów sygnałów i może, ale nie musi, być w stanie wykonać dowolną konwersję formatu.}

edycja: Jak wspomniał Péter Török, wykres niekoniecznie będzie drzewem, schemat jest prostym przykładem ilustrującym ten pomysł. Po wdrożeniu w „świecie rzeczywistym” może istnieć wiele ścieżek, które oferują różne poziomy definicji (DVI> VGA> komponent> kompozyt), które planowałem reprezentować za pomocą ważenia krawędzi.

edycja 2: Oto nieco bardziej kompleksowy przykład ze wskazaną kierunkowością i pokazujący sieć składającą się z dwóch typów sygnałów. Początkowy przykład został nieznacznie zmodyfikowany, tak aby każde wejście i wyjście w urządzeniu było zdefiniowane jako dyskretny węzeł, ponieważ zapewni to dane wymagane do sterowania routingiem macierzy / wyborem wejścia.

To jest drzewo, Dijkstra to przesada O ( n ^ 2 ). Trywialne O ( n ) pierwsze wyszukiwanie szerokości jest wystarczające.

EDYCJA: Uruchom BFS w dowolnym węźle ze stopniem co najmniej dwa.

EDYCJA 2: Ponieważ nie gwarantuje się, że wykres będzie drzewem, użyj Dijkstry, jeśli chcesz trochę zoptymalizować, możesz najpierw „rozebrać” wykres wszystkie wierzchołki stopnia pierwszego (dla nich ścieżka jest trywialna), w tym te które zdarzają się zdobyć stopień pierwszy z powodu rozebrania byłych sąsiadów, a resztą zajmują się Dijkstra (która jest dokładnie częścią „nieposiadającą drzewa”).

Poza tym powiedziałbym, że chcesz ścieżek z każdego węzła do siebie, prawda? Algorytm Dijsktry wykonuje tylko ścieżki od jednego do wszystkich innych. Być może wykonaj algorytm Floyda-Warshalla na odpędzonej części. Oczywiście, jeśli topologia jest bardzo dynamiczna, najlepiej wykonać (usuwanie i) Dijkstra, ad hoc.

Możesz przeszukiwać dany wykres za pomocą A * (bardziej ogólnej formy algorytmu Dijkstry). W swoim komentarzu wspominasz o kosztach ważenia:

Przyłączeniowy. Teoria ta pozwoli na takie zdefiniowanie, że im wyższa definicja ścieżki sygnału, tym mniejsza waga. Krawędzie łączące węzły wykonujące konwersję formatu otrzymałyby wówczas wagę wyższą niż przypisana do krawędzi łączących węzły nieodwracające. Spowodowałoby to skierowanie sygnału w jego natywnym formacie, jeśli to możliwe, obejmując jedynie konwersję formatu (i związaną z tym degradację sygnału i wykorzystanie sprzętu), gdy jest to konieczne

Jeśli dobrze to rozumiem, chcesz znaleźć ścieżkę o najniższym koszcie od początku do celu. Jeśli podasz każdemu węzłowi zarówno rzeczywisty koszt, jak i szacunkową (heurystyczną) wartość docelową (która jest zarówno dopuszczalna, jak i spójna), wówczas A * gwarantuje optymalne rozwiązanie. Może to być przesada, w zależności od tego, jak dobrze rozumiem twój problem.