Ich benutze Bellman-Ford, um den kürzesten Weg durch ein Diagramm mit einigen negativen Gewichten zu finden. Das Diagramm hat keine Möglichkeit für Schleifen und keine bidirektionalen Verbindungen. Ich möchte die K kürzesten Pfade durch den Graphen finden, wo die Pfade keine gemeinsamen Knoten haben. Gibt es einen Algorithmus, den ich nachschlagen kann, um zu lernen, wie man das macht? Eine einfache Implementierung ist momentan wichtiger als die Geschwindigkeit.Algorithmus, um Top-K-Pfade im Graphen zu finden, ohne gemeinsame Ecken, negative Gewichte?
Hinzugefügt: Danke für Kommentare. Um klar zu sein, suche ich nach den besten K Möglichkeiten, um von einem bestimmten Startknoten zu einem bestimmten Endknoten zu gelangen, ohne dass andere Knoten gemeinsam sind. Ich brauche ein globales Optimum; Das sequentielle Finden der besten und Löschen von Knoten ergibt kein befriedigendes Ergebnis. Dieser: https://en.wikipedia.org/wiki/Yen%27s_algorithm, gibt den Geschmack von dem, worüber ich spreche, aber in diesem Fall erfordert es nicht-negative Randkosten und es erlaubt auch Knoten geteilt werden.
Ich nehme an, der Graph kann als verbunden angenommen werden? – Codor
K kürzeste Pfade, die keine gemeinsamen Knoten haben, wie in den K kürzesten Pfaden, die zwei Scheitelpunkte verbinden und nur diese beiden Scheitelpunkte teilen? Wenn der Graph loopless ist, könnten Sie alle Pfade ausschöpfen und den kürzesten K nehmen? – opticaliqlusion
Sie haben also eine gerichtete azyklische Grafik? Suchen Sie jetzt immer wieder nach einem kürzesten Pfad und löschen Sie die inneren Knoten oder sind Sie an einer globalen Optimierung interessiert? –