Ich bin in der Lage, this algorithm zu verwenden, um den längsten Pfad in einer gewichteten DAG zu finden (mit topologischen Sortierung und dann Entspannung jeder Kante). Meine Frage ist jetzt, ob es einen Algorithmus gibt, um die 3 längsten Pfade der DAG zu finden? Oder gibt es eine Javascript- oder Java-Bibliothek, die diesen Algorithmus implementiert?Suche nach Top 3 längsten Pfad in gerichteten azyklischen gewichteten Graphen
Sie können ganz einfach Längstes Weg berechnen, und Sie können für die Suche nach der nächsten längsten Pfad folgenden Algorithmus verwenden:
löschen jede Kante des Haupt längsten Weg eins nach dem anderen und dem Lauf wieder der Algorithmus die längste zu finden Pfad auf dem modifizierten Graphen setzen Sie dann die gelöschte Kante zurück und löschen Sie eine andere Kante.
Warum funktioniert das? Sie benötigen einen Pfad, der nicht genau der erste längste Pfad ist, also muss der zweitlängste Pfad an mindestens einer Kante unterschiedlich sein. Wenn Sie also eine Kante ignorieren, finden Sie den längsten Pfad für jede der gefundenen Kanten ein längster Pfad, der nicht mindestens eine Kante mit dem längsten Hauptpfad teilt.
Der drittlängste Pfad ist ein Pfad, der der längste Pfad ist und nicht mindestens eine Kante mit dem ersten und dem zweitlängsten Pfad teilt.
Ich bin vielleicht falsch, aber ich glaube, der einzige Algorithmus, der dies tun würde, wäre, alle möglichen Pfade zu generieren, nach Pfadlänge zu sortieren und dann die gewünschten Pfade auszuwählen. Die Alternative wäre, den längsten Pfad zu finden und dann das Diagramm so zu modifizieren, dass dieser Pfad in den oberen 3 nicht mehr existiert, aber keine anderen Pfade modifiziert und dann iteriert wird - dies ist im Allgemeinen wahrscheinlich nicht möglich, obwohl es möglicherweise eine bestimmte Unterklasse von Graphen gibt, wo es möglich sein könnte. – twalberg
Ich habe nicht genug Zeit, um meine Idee jetzt zu erzählen, aber ich erkläre es mehr in drei Tagen, die Hauptidee ist, dass Sie den längsten Pfad finden müssen, der eine oder mehrere Kanten nicht mit dem längsten längsten Pfad teilt Sie müssen also nur den Algorithmus für den Graphen abzüglich jeder der Kanten des längsten Hauptpfads ausführen. – FazeL