Algoritmo di Dijkstra per pesi negativi

Question

Ok, prima di tutto so che Dijkstra non funziona con pesi negativi e possiamo usare Bellman-ford invece di farlo. Ma in un problema mi è stato dato afferma che tutti i bordi hanno pesi da 0 a 1 (0 e 1 non sono inclusi). E il costo del percorso è in realtà il prodotto.

Quindi quello che stavo pensando è solo prendere il registro. Ora tutti i bordi sono negativi. Ora so che Dijkstra non funzionerà con pesi negativi, ma in questo caso tutti i bordi sono negativi, quindi non possiamo fare qualcosa in modo che Dijkstra funzioni.

Mi sembra di moltiplicare tutti i pesi di -1 ma poi il percorso più breve diventa il percorso più lungo.

Quindi è comunque possibile evitare l'algoritmo Bellman-Ford in questo caso.

La domanda esatta è: "Supponiamo che per alcune applicazioni il costo di un percorso sia uguale al prodotto di tutti i pesi dei bordi del percorso. Come utilizzeresti l'algoritmo di Dijkstra in questo caso? Tutti i pesi del i bordi sono da 0 a 1 (0 e 1 non sono inclusi). "

Answer 1

Quindi si desidera utilizzare una funzione, diciamo F, che verrà applicata ai pesi del grafico originale e quindi con l'algoritmo di Dijkstra troverete il percorso del prodotto più breve. Consideriamo anche il seguente grafico che si parte dal nodo A e dove 0 < x < y < 1:

Nel grafico sopra F(x) deve essere minore di F(y) per l'algoritmo di Dijkstra all'uscita correttamente i percorsi più brevi da A.

Ora, diamo un grafico leggermente diverso che si ricomincia dal nodo A:

allora come l'algoritmo di Dijkstra funzionerà?

Dal F(x) < F(y) quindi selezioneremo il nodo B al passaggio successivo. Quindi visiteremo il nodo rimanente C.L'algoritmo di Dijkstra mostrerà che il percorso più breve da A a B è A -> B e il percorso più breve da A a C è A -> C.

Ma il percorso più breve da A a B è A -> C -> B con costo x * y < x.

Ciò significa che non possiamo trovare una funzione di trasformazione del peso e aspettiamo che l'algoritmo di Dijkstra funzioni in ogni caso.

Answer 2

Se tutti i pesi sul grafico sono nella gamma (0, 1), quindi ci sarà sempre un ciclo il cui peso è di meno che 1, e quindi sarà bloccato in questo ciclo per sempre (ogni passano sul ciclo riduce la peso totale del percorso più breve). Probabilmente hai frainteso il problema e vuoi trovare il percorso più lungo, oppure non ti è permesso visitare lo stesso vertice due volte. Ad ogni modo, nel primo caso l'algoritmo dijkstra'a è sicuramente applicabile, anche senza la modifica log. E sono abbastanza sicuro che il secondo caso non può essere risolto con la complessità polinomiale.

Answer 3

Hai scritto:

ho pensato di moltiplicare tutti i pesi di -1 ma poi il percorso più breve diventa il percorso più lungo.

Per alternare tra il percorso più breve e quello più lungo, invertire i pesi. Quindi 1/3 sarà 3, 5 sarà 1/5 e così via.

Answer 4

Se il tuo grafico ha cicli, nessun algoritmo di percorso più breve troverà una risposta, perché quei cicli saranno sempre "cicli negativi", come ha sottolineato Rontogiannis Aristofanis.

Se il grafico non ha cicli, non è necessario utilizzare Dijkstra a tutti.

Se è diretto, è un DAG e ci sono algoritmi di percorso più breve tempo lineare.

Se è non orientato, è un albero, ed è banale trovare il percorso più breve tra gli alberi. E se il tuo grafico è diretto, anche senza cicli, Dijkstra continua a non funzionare per lo stesso motivo per cui non funziona con il grafico del bordo negativo.

In tutti i casi, Dijkstra è una scelta terribile di algoritmo per il tuo problema.