Grundlegende Unterschiede zwischen den Problemen am weitesten und am längsten Pfad - Graph, Theorie, längster Pfad

Was sind die Unterschiede zwischen dem breitesten Pfad?und längste Pfadfragen? Genauer gesagt, warum kann ersteres gelöst werden, indem der maximale aufspannende Baum gefunden wird, während letzteres nicht möglich ist. Ich weiß, wenn ich den maximalen Spannbaum herausziehe, ist es sofort offensichtlich, dass er nicht unbedingt den längsten Pfad enthält, aber ich kann mir nicht vorstellen, was die Unterschiede zwischen den beiden Fragen sind, die diese Tatsache bestätigen.

Vielen Dank.

Antworten:

Der Hauptunterschied zwischen diesen beiden Problemen besteht darin, dass das Problem mit dem breitesten Pfad eine optimale Unterstruktur aufweist, während das Problem mit dem längsten Pfad (nach bestem Wissen) nicht auftritt.

Betrachten Sie insbesondere den breitesten Pfad von aKnoten U zu einem Knoten v. Wenn dieser Pfad einen Zwischenknoten s passiert, dann muss der breiteste Pfad von u zu v aus einem breitesten Pfad von u nach s bestehen, gefolgt von einem breitesten Pfad von s nach v. Wenn nicht Dann könntest du entweder einen Teil des Pfades von u zu s oder von s zu v mit einem noch breiteren Pfad ersetzen, ohne die Lösung zu verschlechtern.

Dies funktioniert jedoch nicht für das Problem mit dem längsten Pfad. Wenn Sie den längsten Pfad (implizit den längsten einfachen Pfad) von u zu v nehmen und einige Knoten passieren, tun Sie dies nicht unbedingt den längsten Weg von U nach S gefolgt von dem längsten Weg von S nach V haben. Hier ein Beispiel:

   2
u --- v
1  / 3
s

Der längste Weg von u nach s besteht aus dem Weg u - v - s (Länge 5), während der längste Weg von u nach v u - s - v (Länge 4) ist.

Diese optimale Unterstruktur macht es möglichmöglich, gierige Algorithmen und (effiziente) dynamische Programmierung zu verwenden, um das breiteste Pfadproblem effizient zu lösen, aber (nach bestem Wissen) nicht in der Lage, das längste Pfadproblem effizient zu lösen der Weg (wenn der kürzeste Weg von u nach v durch s geht, haben Sie die Verkettung der kürzesten Wege von u nach s und von s nach v), und Sie können ähnliche gierige Algorithmen oder DP verwenden, um auch kürzeste Wege zu bestimmen.

Hoffe das hilft!