Ricerca del percorso con la capacità minima massima nel grafico

Question

Sto aiutando un amico con un progetto correlato al lavoro in cui, ha bisogno di calcolare la capacità massima da un nodo a a un nodo b, dove il bordo ha una capacità. Tuttavia, la capacità massima in un percorso da a a b è limitata dal bordo con la capacità più bassa.

Vorrei cercare di spiegare con un semplice campione di

modo che il grafico è un grafo orientato con bordi ponderati, e può essere ciclica. Il percorso con la più alta capacità sarebbe s-> b-> t e avrà la capacità di 250, poiché quel limite sta impostando il limite.

Ho letto un po 'di lettura e ho scoperto che questo tipo di problema è un "Widest path problem" o lo definirei come un percorso con la capacità minima massima, ma non ho trovato alcun esempio o pseudo codice che spieghi come per affrontare questo.

Stavo pensando qualcosa sulla ricerca di tutti i percorsi da s a t, usando BFS e in qualche modo solo per consentire di visitare un nodo una volta in un percorso, e poi trovare il valore minimo nel percorso, funzionerebbe?

Answer 1

Vorrei usare qualche variante di Dijkstra's. Ho preso la pseudo codice qui sotto direttamente da Wikipedia e cambiato solo 5 piccole cose:

1. Rinominato dist-width (dalla linea 3 a)
2. inizializzato ogni width--infinity (linea 3)
3. inizializzato la larghezza della sorgente di infinity (linea 8)
4. Impostare il criterio di finitura per -infinity (linea 14)
5. modificato la funzione di aggiornamento e il segno (linea 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 

Alcuni (handwaving) spiegazione del perché questo funziona: si inizia con la fonte. Da lì, hai una capacità infinita per se stesso. Ora controlli tutti i vicini della fonte. Supponiamo che i bordi non abbiano tutti la stessa capacità (nell'esempio, ad esempio (s, a) = 300). Quindi, non esiste un modo migliore per raggiungere b quindi tramite (s, b), in modo da conoscere la migliore capacità del caso di b. Continui ad andare ai migliori vicini del noto gruppo di vertici, fino a raggiungere tutti i vertici.

Answer 2

La risposta sopra è stata spiegata molto bene. Solo nel caso qualcuno ha bisogno di una spiegazione della correttezza dell'algoritmo, qui si va:

Dimostrazione:

In qualsiasi punto l'algoritmo, ci saranno 2 set di vertici A e B. I vertici in A saranno i vertici in cui è stato trovato il percorso della capacità minima massima corretta. E impostare B ha vertici a cui non abbiamo trovato la risposta.

Ipotesi induttiva: in qualsiasi fase, tutti i vertici nell'insieme A hanno i valori corretti del percorso di capacità minima massima. es., tutte le iterazioni precedenti sono corrette.

Correttezza del caso base: Quando l'insieme A ha solo il vertice S. Quindi il valore su S è infinito, che è corretto.

In iterazione corrente, abbiamo impostato

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

induttivo passo: Supponiamo che W sia il vertice nell'insieme B con la val maggiore [W]. E W viene rimosso dalla coda e W è stato impostato per la risposta val [W].

Ora, è necessario mostrare che ogni altro percorso S-W ha una larghezza < = val [W]. Questo sarà sempre vero perché tutti gli altri modi di raggiungere W passeranno attraverso un altro vertice (chiamiamolo X) nel set B.

E per tutti gli altri vertici X nel set B, val [X] < = val [ W]

Quindi qualsiasi altro percorso su W sarà vincolato da val [X], che non è mai maggiore di val [W].

Quindi la stima corrente di val [W] è ottimale e quindi l'algoritmo calcola i valori corretti per tutti i vertici.