Mindestkantengewicht entlang eines Pfads

Question

Wie würde ich das Maximum einer Reihe minimaler Kantengewichte entlang aller möglichen Pfade zwischen beliebigen Eckpunkten finden? (u,v)?

Ich dachte an eine Modifikation von Floyd-Warshall?

i.e. Path 1: s - a - b - c - d - t with weights 1 - 5 - 6 - 10 - 9

Das minimale Kantengewicht beträgt 1

Path 2: s - x - y - z - w - t with weights 3 - 9 - 8 - 6 - 7

Das minimale Kantengewicht beträgt 3

So ist das Ergebnis max(1, 3) = 3

Answer 1

Ja, eine Modifikation von Floyd-Warshall würde funktionieren – statt der kürzesten Pfadlänge behalten Sie die maximale Pfad-„Breite“ im Auge.

Wenn Sie nur an zwei Eckpunkten interessiert sind, können Sie einen einfacheren Ansatz wählen:Beginnen Sie mit einem leeren Diagramm und fügen Sie Kanten nach ihrem Gewicht sortiert hinzu (von hoch nach niedrig).Wenn die betreffenden Knoten verbunden werden, ergibt die letzte hinzugefügte Kante die maximale „Breite“.Richtig gemacht (d. h.Verwenden eines disjunkten Satzes zur Überprüfung der Verbundenheit), dies ist schneller als Floyd-Warshall.

Notiz:Ich denke nur an positive Gewichte.