sna: Änderung des Dijkstra-Algorithmus (kürzeste Wege)

Question

Ich habe die Funktion shortest_paths aus dem Paket igraph verwendet, um den kürzesten Weg zwischen zwei Verbindungen zu berechnen.

Mein igraph Objekt enthält die gewichteten Links.

Der integrierte Dijkstra-Algorithmus verwendet Summen, um den kürzesten Pfad auszudrücken.

Wie kann ich das Produkt anstelle der Summe verwenden?

Answer 1

Log ist eine monoton steigende Funktion, so dass der Pfad, der das Produkt der Kantengewichte minimiert, auch den Logarithmus des Produkts der Kantengewichte oder äquivalent die Summe des Logarithmus der Kantengewichte minimiert. Daher können Sie die Kantengewichtungen einfach durch ihre Protokollumwandlung ersetzen und die Funktion für den kürzesten Pfad verwenden.