Problema del percorso di capacità massimo con vincoli

Question

Stavo cercando di sviluppare un algoritmo per il problema della massima capacità con i vincoli ma non è riuscito a capire le modifiche necessarie richieste per la corretta output. Il problema è:
fornito un grafico non rilevato con due parametri (peso, costo).Abbiamo bisogno di trovare il Problema del percorso di capacità massimo da Source a Destinazione in modo tale che il costo del percorso (somma dei bordi del percorso) sia in un valore fisso specificato dall'utente.In altre parole, (la somma del parametro dei costi lungo il percorso) è delicato con il limite superiore da un valore costante.
Ho modificato l'algoritmo esistente aggiungendo e il vincolo di costo aggiuntivo mentre si rilassano i bordi ma non è stato in grado di farlo funzionare per tutti i tipi di grafico.Mi stavo anche chiedendo se questo problema è completo.

Answer 1

Può essere risolto in tempo polinomiale.Ad esempio, è possibile utilizzare la ricerca binaria sul peso.Dato un peso candidato, elimina tutti i bordi con un peso inferiore, quindi trovare il percorso del costo più basso e verificare se il suo costo è inferiore al limite inferiore;Ciò ti dice se il peso era troppo alto o troppo basso.Ripeti fino a quando la ricerca binaria converge.