Ich möchte NetzwerkX finden die absolut längste Weg in meiner gerichteten, azyklischen Grafik.networkx: effizient finden absolut längsten Weg in Digraph
Ich weiß über Bellman-Ford, also negierte ich meine Graphenlängen. Das Problem: networkx bellman_ford() erfordert einen Quellknoten. Ich möchte den absoluten längsten Pfad (oder den kürzesten Pfad nach der Negation) finden, nicht den längsten Pfad von einem bestimmten Knoten.
Natürlich könnte ich bellman_ford() auf jedem Knoten in der Grafik und sortieren, aber gibt es eine effizientere Methode?
Von dem, was ich gelesen habe (zB http://en.wikipedia.org/wiki/Longest_path_problem) Ich weiß, dass es eigentlich nicht eine effizientere Methode sein kann, aber frage mich, ob jemand irgendwelche Ideen hatte (und/oder hatte P = NP (grins) bewiesen).
EDIT: alle Kantenlängen in meinem Graph sind +1 (oder -1 nach der Negation), so eine Methode, die einfach die meisten Knoten besucht, würde auch funktionieren. In der Regel wird es nicht möglich sein, ALLE Knoten zu besuchen.
EDIT: OK, ich erkannte gerade, dass ich einen zusätzlichen Knoten hinzufügen könnte, der einfach mit jedem anderen Knoten im Diagramm verbindet, und dann bellman_ford von diesem Knoten ausführen. Irgendwelche anderen Vorschläge?
Dies ist keine Hausaufgabe. Sicher würde Networkx diesen Algorithmus implementieren?Ich habe Ihren Link ausprobiert und es scheint, dass Sie sich anmelden müssen. – barrycarter
Ich habe mit Code aktualisiert. Du hast Recht - diese Verbindung ist schlecht. Es sollte andere Referenzen geben - vielleicht können wir eine gute finden. – Aric
Es stellt sich heraus, dass mein Graph bereits topologisch sortiert ist, und dass ich das Problem lösen kann, ohne networkx zu verwenden (indem ich den längsten eingehenden Pfad pro Knoten und den vorherigen Knoten für jeden dieser Pfade beobachte, wie Sie darauf hinweisen). Kann nicht glauben, dass es so einfach ist! – barrycarter