Algoritmo per trovare i percorsi K in alto nel grafico, senza vertici comuni, pesi negativi?

Question

Sto utilizzando Bellman-Ford per trovare il percorso più breve attraverso un grafico con alcuni pesi negativi. Il grafico non ha possibilità di loop e nessuna connessione bidirezionale. Mi piacerebbe trovare i cammini più corti di K attraverso il grafico, in cui i percorsi non condividono nodi in comune. C'è un algoritmo che posso cercare per imparare come farlo? La semplice implementazione è più importante della velocità al momento.

Aggiunto: Grazie per i commenti. Per essere chiari, sto cercando i migliori K modi per passare da un nodo iniziale specificato a un nodo finale specificato, senza altri nodi in comune. Ho bisogno di un optimum globale; trovare in modo sequenziale i nodi migliori e eliminarli non dà un risultato soddisfacente. Questo: https://en.wikipedia.org/wiki/Yen%27s_algorithm, dà il sapore di ciò di cui sto parlando, ma in questo caso richiede costi di bordo non negativi e consente anche la condivisione dei nodi.

Answer 1

Penso che il problema possa essere risolto trovando un flusso minimo di costi.

Trasformiamo il grafico nel modo seguente:

1. sostituire ogni nodo v tranne source e lavello con due nodi v1 e v2 collegati da un bordo di peso 0 da v1 a v2. I archi entranti della ex v entrano a v1 e l'uscita partono dal v2. Con questo il problema è equivalente a non usare quei bordi più di una volta.

2. Impostare la capacità 1 su tutti i bordi.

Trovare un flusso di valore K vi darà K percorsi che non condividono un nodo (a causa di mettere la capacità di 1 a quei nuovi bordi). Quindi, se questo flusso è un flusso di costo minimo, si avrà che quei percorsi K hanno anche la somma minima possibile di costi.

Si presume che non si disponga di uno spigolo che collega direttamente la sorgente e il lavandino. Controlla la cassa dell'angolo separatamente.