Suche nach Pfad mit maximaler Mindestkapazität in Grafik

Question

Ich helfe einem Freund mit einem Arbeitsprojekt, wo er die maximale Kapazität von einem Knoten A zu einem Knoten b berechnen muss, wo die Kante eine Kapazität hat. Die maximale Kapazität in einem Pfad von a nach b ist jedoch durch die Kante mit der niedrigsten Kapazität begrenzt.

Lassen Sie mich versuchen, mit einem einfachen Beispiel

So ist die grafische Darstellung zu erklären, ist ein gerichteter Graph mit gewichteten Kanten, und es kann zyklisch sein. Der Pfad mit der höchsten Kapazität wäre s-> b-> t und hätte die Kapazität von 250, da diese Kante das Limit festlegt.

Ich habe ein wenig gelesen und herausgefunden, dass diese Art von Problem ist ein "Widest path problem" oder ich würde es so etwas wie einen Pfad mit maximaler Mindestkapazität nennen, aber ich habe keine Beispiele oder Pseudo-Code, der erklärt, wie um das anzugehen.

Ich dachte etwas in den Linien der Suche nach allen Pfaden von s nach t, ​​mit BFS und irgendwie nur um einen Knoten einmal in einem Pfad zu besuchen, und dann den Mindestwert im Pfad finden, würde das funktionieren?

Answer 1

Ich würde eine Variante von Dijkstra's verwenden. Ich nahm den Pseudo-Code unten direkt aus Wikipedia und verändern nur 5 kleine Dinge:

1. Umbenannt dist-width (von der Linie 3 auf)
2. Initialized jeden width--infinity (Linie 3)
3. die Breite Initialized von der Quelle zu infinity (Linie 8)
4. das Zielkriteriums -infinity (Zeile 14) Satz
5. die Update-Funktion und den Vorzeichens Modified (Zeile 20 + 21)
01.235.

1 function Dijkstra(Graph, source): 
2  for each vertex v in Graph:         // Initializations 
3   width[v] := -infinity ;        // Unknown width function from 
4                 // source to v 
5   previous[v] := undefined ;        // Previous node in optimal path 
6  end for              // from source 
7  
8  width[source] := infinity ;         // Width from source to source 
9  Q := the set of all nodes in Graph ;      // All nodes in the graph are 
10                 // unoptimized – thus are in Q 
11  while Q is not empty:          // The main loop 
12   u := vertex in Q with largest width in width[] ;  // Source node in first case 
13   remove u from Q ; 
14   if width[u] = -infinity: 
15    break ;           // all remaining vertices are 
16   end if             // inaccessible from source 
17   
18   for each neighbor v of u:        // where v has not yet been 
19                 // removed from Q. 
20    alt := max(width[v], min(width[u], width_between(u, v))) ; 
21    if alt > width[v]:         // Relax (u,v,a) 
22     width[v] := alt ; 
23     previous[v] := u ; 
24     decrease-key v in Q;       // Reorder v in the Queue 
25    end if 
26   end for 
27  end while 
28  return width; 
29 endfunction 

Einige (handwaving) Erklärung, warum dies funktioniert: Sie mit der Quelle starten. Von dort hast du unendliche Kapazität für sich. Jetzt überprüfen Sie alle Nachbarn der Quelle. Angenommen, die Kanten haben nicht alle die gleiche Kapazität (in Ihrem Beispiel sagen wir (s, a) = 300). Dann gibt es keinen besseren Weg, um b dann über (s, b) zu erreichen, so dass Sie die beste Fallkapazität von b kennen. Sie fahren fort, zu den besten Nachbarn der bekannten Menge von Knoten zu gehen, bis Sie alle Knoten erreicht haben.

Answer 2

Die obige Antwort wurde sehr gut erklärt. Nur für den Fall jemand eine Erklärung für die Richtigkeit des Algorithmus benötigt, hier gehen Sie:

Beweis:

An jedem Punkt in dem Algorithmus, wird es 2 Sätze von Eckpunkten A und B sein. Die Scheitelpunkte in A sind die Scheitelpunkte, zu denen der richtige Pfad für die maximale minimale Kapazität gefunden wurde. Und Satz B hat Ecken, auf die wir keine Antwort gefunden haben.

Induktive Hypothese: Bei jedem Schritt haben alle Scheitelpunkte in Satz A die korrekten Werte für den maximalen Mindestkapazitätspfad zu ihnen. dh alle vorherigen Iterationen sind korrekt.

Korrektheit des Basiskoffers: Wenn die Menge A nur den Scheitelpunkt S hat. Dann ist der Wert für S unendlich, was korrekt ist.

In aktuellen Iteration setzen wir

val [W] = max (val [W], min (val [V], width_between (VW)))

Inductive Schritt: Angenommen, W ist der Scheitelpunkt in Menge B mit dem größten Wert [W]. Und W wird aus der Warteschlange entfernt und W wurde als Antwort val [W] gesetzt.

Nun müssen wir zeigen, dass jeder andere S-W-Pfad eine Breite < = val [W] hat. Dies wird immer wahr sein, da alle anderen Wege, W zu erreichen, durch einen anderen Scheitelpunkt (nennen wir X) gehen werden.

Und für alle anderen Knoten X in Menge B, val [X] < = val [ W]

Somit wird jeder andere Pfad zu W durch val [X] eingeschränkt, der niemals größer als val [W] ist.

Somit ist die aktuelle Schätzung von val [W] optimal und daher berechnet der Algorithmus die korrekten Werte für alle Ecken.