Domanda di teoria dei grafi, Java. Quale algoritmo per ottenere quanto segue

Question

Ho un grafico, con nodi X e bordi Y. Bordi ponderati. Il punto è iniziare da un nodo e fermarsi a un altro. Ora ecco che arriva il problema;

Visualizza il problema. I bordi sono strade e i pesi dei bordi sono i limiti di peso massimo per i veicoli che guidano sulle strade. Vorremmo guidare il camion più grande possibile da A a B. Quindi il peso massimo consentito per un camion che percorre un determinato percorso è il peso più piccolo di tutti i bordi in quel percorso. Voglio il massimo peso massimo consentito per tutti i percorsi da A a B.

Posso usare una sorta di algoritmo di Dijkstra per questo problema? Non sono sicuro di come esprimere questo problema sotto forma di un algoritmo che posso implementare. Ogni aiuto è molto apprezzato.

Aggiornamento: Ho provato qualcosa che non ha funzionato per me. Un nodo dovrebbe avere un camion massimo per ogni fronte in arrivo.

Answer 1

L'algoritmo di Dijkstra dovrebbe funzionare, ma il tuo " distance " in questo caso è un po 'strano. La tua & Quot; distance & Quot; è il camion di dimensioni massime che puoi raggiungere in un nodo. Chiamiamo M [v] per un nodo v. È necessario elaborare i nodi in ordine dal M [v] più grande al M [v] più piccolo (opposto al normale Dijkstra), e calcolare per ogni fronte e da v a w:

M[w] = max(M[w], min(e.weight, M[v]))

Answer 2

Questo suona (quasi) esattamente come il problema del flusso massimo che può essere risolto in modo efficiente utilizzando l ' algoritmo Ford-Fulkerson .

Come ha sottolineato Keith in un commento, il massimo dell'algoritmo deve essere leggermente modificato per trovare solo un percorso con segmento di percorso minimo massimizzato, poiché il camion può & # 8217; essere diviso in più parti.

Answer 3

Penso che tu stia cercando questo

Percorso più breve

modifica: in realtà no non sei, e il collegamento di flusso massimo è corretto

Answer 4

Quindi, se ho capito bene, mi stai chiedendo " Qual è il più grande camion che può guidare da A a B "

Per applicare l'algoritmo di Dijkstra, avrai bisogno di un modo per modellare " cost " ;. Se si desidera utilizzare un'implementazione standard, è possibile assegnare l'inverso del peso al costo. Pertanto, il margine di costo più elevato è quello con il peso massimo più basso. Ovviamente, dal momento che probabilmente desideri utilizzare numeri interi piacevoli, puoi semplicemente modificare i confronti anziché utilizzare effettivamente le inversioni.

Answer 5

Stai cercando di ottimizzare un [ http://en.wikipedia.org/wiki/Flow_network ] . La capacità è il limite di peso massimo della strada; e il flusso è il peso del camion.

Answer 6

Potresti adottare una sorta di approccio spanning tree minimo. Collegare i nodi un bordo alla volta, prima i bordi del flusso più alto, fino a quando A e B sono collegati. L'ultimo bordo che hai aggiunto al grafico è il margine di flusso più basso che dovrai attraversare per andare da A a B. Probabilmente non è la soluzione più efficiente (O (N ² ) nel caso peggiore) , ma almeno è semplice.

Answer 7

Questo non è né il problema del percorso più breve, né un problema di flusso massimo. In realtà non ci sono problemi. Ha dichiarato: vuoi il peso massimo per tutti i percorsi da A a B. Quindi vai a generare tutti i percorsi da A per BFS. Per tutti i percorsi che terminano in B, trova il peso minimo dei bordi del percorso.

Answer 8

Usa l'algoritmo di Dijkstra con l'inverso del peso massimo del camion come costo del bordo, e il massimo dei pesi dei bordi individuali come costo totale del percorso.

vale a dire. edge_cost è uguale a 1 / (peso massimo del carrello consentito) il total_cost di un determinato percorso è il massimo dei singoli <=> di tutti i bordi del percorso.

Answer 9

Varie risposte sopra suggeriscono semplicemente l'algoritmo Dijkstra con una funzione di peso modificata. Ad esempio, w(e) = -c(e) o 'w (e) = 1 / c (e)', dove w(e) è il peso di un bordo, utilizzato dall'algoritmo e c(e) è la capacità del bordo nel formulazione originale del problema.

Questi non funzionano.

Si possono facilmente creare contro-esempi per ottenere risultati errati. Ad esempio, considera il grafico:

a---3-->b---3--->c---3-->d
 \                       ^
  \                      |
   \----------3----------|

Supponiamo che il valore di a ('distanza del nodo d nella formulazione dell'algoritmo) sia zero. I due percorsi da (-3)+(-3)+(-3) = -9 a -3 sono equivalenti in questo problema. Tuttavia, se si annulla solo la capacità del bordo, la distanza (d), utilizzando il percorso lungo, è (1/3)+(1/3)+(1/3)=1 mentre si utilizza il percorso breve sarebbe (1/3). Se invertiamo la capacità del bordo, la distanza (d) usando il percorso lungo sarebbe +, mentre sarebbe < usando quello breve.

Ciò che funzionerà è modificare la fase di rilassamento dell'algoritmo, ovvero invece di utilizzare le funzioni di addizione (min) e minore di (>), usando rispettivamente le funzioni <= > e maggiore di (@) e utilizza un max-heap anziché un min-heap. Potremmo evitare le ultime due modifiche se annulliamo i pesi del bordo e utilizziamo meno di, ma in nessun modo possiamo evitare di sostituire a @ a = a, poiché abbiamo bisogno di un operatore a=0 dove u per tutti i d(u) valori, mentre <=> funziona solo per <=>.

Quindi, l'unica risposta corretta che vedo è la prima data da Keith Randall.

Un buon esercizio sarebbe dimostrare formalmente che l'algoritmo modificato è corretto. Ciò che deve essere dimostrato è: - se <=> è il nodo con il valore massimo <=> in qualsiasi iterazione di loop, nessun percorso che coinvolge nodi non contrassegnati può creare un percorso per <=> generare una distanza maggiore di <=>.

Intuitivamente è facile da vedere, poiché tutti gli altri nodi non contrassegnati hanno una distanza inferiore (o uguale a) alla distanza di 'u' (perché scegliamo <=> come quello con la distanza massima) e la distanza del i percorsi generati sono prodotti da successive invocazioni di <=>, quindi possono solo diventare più piccoli, non più grandi.