Finden maximale Pfade zwischen 2 Punkten

Question

ein ungerichtete verbundenen Graphen Gegeben hat der Reisende aus node A zu node B mehrmals zu reisen. Jede Kante hat einen positiven Wert und es gibt mehrere Pfade von node A bis node B. Der Wert eines Pfades ist definiert als der Minimalwert aller Kanten in diesem Pfad. Wenn die Reisende aus node A zu node B durch einen bestimmten Pfad gehen, werden die Werte aller Kanten in dem Pfad durch den Wert des Wegs verringert (die in diesem Pfad Minimalwert aller Kanten ist). The goal is to find the set of paths that give the maximum sum of values of all paths traveled.

Beachten Sie die grafische Darstellung kann Zyklen enthalten, aber ein Weg once

Als Beispiel ein Knoten nur besuchen können, sagen, es gibt 4 Knoten A, B, C, D und der Reisende muss gehen zu von A. Angenommen, der eine Wegstrecke A ist ->B ->D und

edge_A_B = 5

edge_B_D = 3

der Wert des Wegs Dann ist

min (edge_A_B, edge_B_D) = 3

und nach der diesen Weg

edge_A_B = 5 Reisen - mit 3 = 0

Und der Reisende die Reise hat A-D wieder - 3 = 2

edge_B_D = 3 aktualisierte Kantenwerte, bis alle Pfade von A bis einen 0-Wert haben.

Answer 1

Ihr Problem ist dem Max-Flow/Min-Cut-Problem sehr ähnlich.

Da die Häufigkeit, mit der Sie jeden Pfad durchlaufen können, durch die Kante mit dem niedrigsten Wert bestimmt wird, wird der Maximalwert durch die Partition ("der Schnitt") des Graphen in zwei kleineren Vertex-Sets V und W begrenzt. während der Startknoten in V und dem Endknoten in W und die Werte aller Kanten ist, die da Dies ist von V nach W. gehen vom Anfang bis zum Ende zu kommen, hat der Reisende einen Rand zu durchqueren, die V und W verbindet, die bedeutet, dass 0, wenn diese Kanten Wert haben, es keine weiteren Wege sind, die der Reisende

prüfen dieses Bild durch die Maxim nehmen:

die richtige Zahl den Wert der Kante darstellt, die linke Zahl der Strömung (oder den Pfad in Ihrem Fall an). Hier ist der Minimalwert des Schnittes 5, die ein vertikaler Schnitt zwischen o und q oder q und t. Daher ist der maximale Fluss (oder in Ihrem Fall der maximale Wert aller zurückgelegten Pfade) ebenfalls 5.Da der Wert des eingehenden Flusses gleich dem Wert des abgehenden Flusses ist (mit Ausnahme des Start- und Endknotens), ist es leicht, die Pfade zu finden, die er danach gegangen ist. In diesem Fall ist es {{s, o, q, t}, {s, o, q, r, t}, {s, p, r, t}}.