Wie das Gewicht kürzesten Pfad in einem Netzwerk bedeuten berechnen

Question

Eingangs

Ich habe ein ungerichteter Graph G (V, E) mit einem Satz von Eckpunkten V und einem Satz von Kanten E. Jede Kante hat eine positive Gewicht w_ij. Es gibt einen Startknoten v_1 und einen Endknoten v_3.

Problem/Algorithmus

Ist es möglich, einen „optimalen“ Weg, mit optimal im Sinne, dass das Gewicht pro verwendet Kante im Weg zu finden minimiert wird? Außerdem sollte kein Knoten mehr als einmal besucht werden.

Beachten Sie, dass der klassische Dijkstra-Algorithmus wird fehlschlagen, weil es für den Weg mit dem geringsten Summe der Gewichte aussieht: Min (Sum (w_ij))

Allerdings habe ich für den Weg suchen, die erfüllt: Min (Sum (w_ij)/number_of_edges)

Beispiel

Zur Verdeutlichung habe ich eine kleine Figur. Rote Zahlen entsprechen Gewichten von Kanten und schwarzen Buchstaben von Scheitelpunkten. Wenn ich den kürzesten Weg zwischen dem Scheitelpunkt v1 und v3 (Bild 1) mit dem Dijkstra-Algorithmus, der kürzeste Weg zu berechnen ist V1-> V2-> v3, da dies gibt das niedrigste Gesamtgewicht:

w = 2 + 2 = 4.

Allerdings würde ich gerne die "mittlere Gewichtung kürzeste Weglänge" haben, so dass das Durchschnittsgewicht pro Schritt des Weges niedriger ist als in jedem anderen Weg . In dem oben erwähnten Beispiel ist der "kürzeste Weg des mittleren Gewichts" v1-> v4-> v5-> v6-> v7-> v3, da das mittlere Gewicht

w = 1/5 (1+ 1 + 1 + 1 + 1) = 1,

während auf dem anderen Pfad ist V1-> V2-> v3 gibt

w = 1/2 (2 + 2) = 2.

Erster Ansatz: Dijkstra Berechnen Sie einfach alle Pfade (ohne Zyklen) zwischen Start- und Endknoten. Berechnen Sie dann das Gesamtgewicht und die Gesamtlänge und teilen Sie sie. Dieser Ansatz wird zu viel Speicher für ein Netzwerk von anständiger Größe benötigen, das ich im Hinterkopf habe (n = 200000).

Zweiter Ansatz: Dijkstra mit gleichzeitiger Längenberechnung den kürzesten Weg (Mindestgewicht Summe) berechnet wird, sparen Sie auch die Länge des bisher Weges. So kennen Sie den aktuellen optimalen Weg zum Gewicht pro Kante.

Frage

1) Gibt es eine Lösung für dieses Problem zu lösen?

2) Wie implementiert man eine Lösung für dieses Problem?

Answer 1

Sie müssen die Kostenfunktion im Dijkstra-Algorithmus ändern, damit dies funktioniert. Berechnen Sie für jeden Knoten den gewünschten Durchschnittswert (anstelle des tatsächlichen Gewichts), und speichern und aktualisieren Sie ihn, wenn Sie neue Knoten aufrufen. Sie sollten zwei Mengen für jeden besuchten Knoten speichern: die average_so_far (anstelle der Länge des kürzesten Pfades, wie zuvor) und number_of_edges (um zu verfolgen, wie viele Kanten bereits in Ihrem Pfad sind). Wenn Sie dies für jeden bereits besuchten Knoten wissen, sollten Sie nach dem Besuch eines neuen Eckpunkts prüfen, ob der neue Durchschnittswert mit einer weiteren Kante (average_so_far*number_of_edges+weight(new edge))/(number_of_edges+1) eine Verbesserung darstellt.

Etwas in dieser Richtung sollte schließlich funktionieren.