Algoritmo di Dijkstra con pesi negativi

Question

È possibile utilizzare l'algoritmo di Dijkstra con pesi negativi?

STOP! Prima di pensare "lol nub puoi saltare infinitamente tra due punti e ottenere un percorso infinitamente economico", sto pensando più a percorsi a senso unico.

Un'applicazione per questo sarebbe un terreno montuoso con punti su di esso. Ovviamente passare dall'alto al basso non richiede energia, infatti, genera energia (quindi un peso percorso negativo)! Ma tornare indietro non funzionerebbe in questo modo, a meno che tu non sia Chuck Norris.

Stavo pensando di incrementare il peso di tutti i punti finché non sono negativi, ma non sono sicuro che funzionerà.

Answer 1

Fintantoché il grafico non contiene un ciclo negativo (un ciclo diretto i cui pesi di bordo hanno una somma negativa), avrà un percorso più breve tra due punti qualsiasi, ma l'algoritmo di Dijkstra non è progettato per trovarli. L'algoritmo più conosciuto per la ricerca di percorsi più brevi a sorgente singola in un grafico diretto con pesi di bordo negativi è lo Bellman-Ford algorithm. Questo ha un costo, tuttavia: Bellman-Ford richiede O (| V | · | E |) tempo, mentre Dijkstra's richiede O (| E | + | V | log | V |) tempo, che è asintoticamente più veloce per entrambi sparsi grafici (dove E è O (| V |)) e grafici densi (dove E è O (| V |^2)).

Nel tuo esempio di un terreno montagnoso (necessariamente directed graph, dal momento che va su e giù per un pendio avere pesi diversi) non v'è alcuna possibilità di un ciclo negativo, dal momento che ciò implicherebbe lasciando un punto e poi tornare ad essa con una guadagno netto di energia - che potrebbe essere utilizzato per creare un perpetual motion machine.

Aumentare tutti i pesi di un valore costante in modo che non siano negativi non funzionerà. Per vedere questo, considera il grafico in cui ci sono due percorsi da A a B, uno che attraversa un singolo bordo di lunghezza 2 e uno che attraversa i bordi di lunghezza 1, 1 e -2. Il secondo percorso è più breve, ma se aumenti tutti i pesi del bordo di 2, il primo percorso ora ha lunghezza 4 e il secondo percorso ha lunghezza 6, invertendo i percorsi più corti. Questa tattica funzionerà solo se tutti i percorsi possibili tra i due punti usano lo stesso numero di bordi.

Answer 2

Se si legge la prova di ottimalità, una delle ipotesi formulate è che tutti i pesi sono non negativi. Quindi, no. Come Bart consiglia, usa Bellman-Ford se non ci sono cicli negativi nel tuo grafico.

Devi capire che un fronte negativo non è solo un numero negativo --- implica una riduzione nel costo del percorso. Se aggiungi un margine negativo al tuo percorso, hai ridotto il costo del percorso --- se aumenti i pesi in modo che questo bordo sia ora non negativo, non ha più quella proprietà di riduzione e quindi questo è un grafico diverso.

Vi incoraggio a leggere la dimostrazione di ottimalità --- lì vedrete che l'ipotesi che l'aggiunta di un bordo a un percorso esistente non può che aumentare (o non influire) il costo del percorso è fondamentale.

Answer 3

È possibile utilizzare Dijkstra su un grafico ponderato negativo, ma è necessario prima trovare l'offset corretto per ciascun vertice. Questo è essenzialmente ciò che fa l'algoritmo di Johnson. Ma quello sarebbe eccessivo poiché Johnson usa Bellman-Ford per trovare l'offset di peso (s). Johnson's è progettato per tutti i percorsi più brevi tra coppie di Vertices.

http://en.wikipedia.org/wiki/Johnson%27s_algorithm

Answer 4

In realtà credo che funzionerà per modificare i pesi bordo. Non con un offset ma con un fattore. Si supponga invece di misurare la distanza che si sta misurando il tempo richiesto dal punto A al punto B.

peso = tempo = distanza/velocità

Si potrebbe anche adattare la velocità in funzione della pendenza di utilizzare quello fisico, se il vostro compito è per vere montagne e auto/bici.

Answer 5

Sì, si potrebbe farlo con l'aggiunta di un passo alla fine cioè

  If v ∈ Q, Then Decrease-Key(Q, v, v.d) 
      Else Insert(Q, v) and S = S \ {v}. 

Answer 6

un albero di espressione è un albero binario in cui tutte le foglie sono operandi (costanti o variabili), ed i nodi non foglia sono operatori binari (+, -, /, *, ^). Implementare questo albero per modellare i polinomi con i metodi di base dell'albero, tra cui:

1. Una funzione che calcola la prima derivata di un polinomio.
2. Valutare un polinomio per un valore specificato di x.

[20] Utilizzare le seguenti regole per la derivata: derivativo (costante) = 0 derivativo (x) = 1 derivativo (P (x) + Q (y)) = derivativo (P (x)) + Derivata (Q (y)) Derivata (P (x) - Q (y)) = Derivata (P (x)) - Derivata (Q (y)) Derivata (P (x) * Q (y)) = P (x) * Derivata (Q (y)) + Q (x) * Derivata (P (x)) Derivata (P (x)/Q (y)) = P (x) * Derivata (Q (y)) - Q (x) * Derivata (P (x)) Derivata (P (x)^Q (y)) = Q (y) * (P (x)^(Q (y) - 1)) * Derivata (Q (y))

Answer 7

Esiste effettivamente un algoritmo che utilizza l'algoritmo di Dijkstra in un ambiente con percorso negativo; lo fa rimuovendo tutti i bordi negativi e ribilanciando prima il grafico. Questo algoritmo è chiamato "Algoritmo di Johnson".

Il modo in cui funziona è aggiungendo un nuovo nodo (diciamo Q) che ha il costo di attraversare ogni altro nodo nel grafico. Quindi esegue Bellman-Ford sul grafico dal punto Q, ottenendo un costo per ciascun nodo rispetto a Q che chiameremo q [x], che sarà 0 o un numero negativo (poiché ha utilizzato uno dei percorsi negativi).

E.g. a -> -3 -> b, quindi se aggiungiamo un nodo Q che ha costo 0 per tutti questi nodi, allora q [a] = 0, q [b] = -3.

Quindi riequilibriamo i bordi utilizzando la formula: peso + q [fonte] - q [destinazione], quindi il nuovo peso di a-> b è -3 + 0 - (-3) = 0. Facciamo questo per tutti gli altri spigoli nel grafico, quindi rimuovi Q ei suoi bordi in uscita e voilà! Ora abbiamo un grafico ribilanciato senza bordi negativi su cui possiamo eseguire dijkstra!

Il tempo di esecuzione è O (nm) [facchino-ford] + nx O (m log n) [n Dijkstra] + O (n^2) [calcolo del peso] = O (nm log n)

Altre informazioni: http://joonki-jeong.blogspot.co.uk/2013/01/johnsons-algorithm.html