Esistono algoritmi più veloci di Dijkstra?

Dato un grafico diretto, connesso con solo pesi di bordo positivi, ci sono algoritmi più veloci per trovare il percorso più breve tra due vertici, rispetto a Dijkstra usando un heap di Fibonacci?Esistono algoritmi più veloci di Dijkstra?

Wikipedia dice che Dijkstra è in O (| E | + | V | * log (| V |)) (utilizzando un heap di Fibonacci).

Non sto cercando ottimizzazioni che, ad esempio, metà del tempo di esecuzione, ma piuttosto algoritmi che si trovano in una complessità temporale diversa (come passare da O (n * log n) a O (n)).

Inoltre, mi piacerebbe conoscere la vostra opinione sul seguente approccio:

Determinare il MCD di tutti i pesi di bordo.
Trasforma il grafico in un grafico con pesi di bordo uniformi.
Utilizzare BFS per trovare il percorso più breve tra due vertici dati.

Esempio per il punto 2:
Imagine GCD a 1. Poi trasformerebbe bordo
A ---> B (peso bordo 3)
in
A-> A '-> A' '-> B (3 volte di spigolo 1)
Questa trasformazione costa un tempo costante e dovrebbe essere eseguita una volta per ogni spigolo. Quindi mi aspetto che questo algoritmo sia in O (| E |) (trasformazione) + O (| E | + | V |) (BFS) = O (2 * | E | + | V |) = O (| E | + | V |)

Grazie per aver trovato il tempo di leggere la mia domanda e spero di non aver stretto il tuo tempo ^^. Buona giornata.

fonte

2009-11-09 Dave O.

Penso che ti stai dimenticando di rendere conto del costo del GCD. –

La trasformazione non viene eseguita in tempo costante. Dovrai creare un numero variabile di nuovi vertici. –

Il GCD sarebbe il miglior valore da usare, ma si può sempre ricorrere indietro e usare solo 1, in modo che non venga speso tempo per il passaggio 1. –

La grande analisi che hai fatto per il tuo algoritmo è profondamente errata. Supponiamo che tutti i bordi siano numeri primi. Il numero di spigoli nel nuovo grafico sarà uguale alla somma di tutti i pesi. Pertanto il O(|E| + |V|) del nuovo nuovo grafico è in realtà O(W x |E| + |V|) nel grafico originale che può essere molto più grande di O(|E| + |V| log |V|).

fonte

2009-11-09 14:22:11

Sei corretto. Nel peggiore dei casi, tutti i pesi degli spigoli sono numeri primi e il grafico è completo. Quindi W è almeno | V |^2 (| V |^2 bordi con pesi> = 1). Quindi il mio algoritmo funziona in | V |^2 * | V |^2 + | E | = | V |^4 + | E | almeno. Tuttavia, la mia domanda originale rimane senza risposta. –

Sry, intendevo | V |^4 + | V | - perché non posso modificare il mio post oi miei commenti? –

Non sono sicuro se esiste un algoritmo asintoticamente più veloce per i grafici arbitrari. Il più veloce che conosco è Dijkstra con gli heap di Fibonacci. Non posso essere sicuro però. –

C'è un algoritmo che ha O (1): Trasforma i pesi in lunghezze di catena e usa i portachiavi per i nodi (veri e propri portachiavi come quelli nella tua tasca). Collegare i portachiavi con le catene giuste. Seleziona i due nodi e allontanali l'uno dall'altro.

Seguire le catene tese da un nodo all'altro. Questo è il percorso più breve.

Per attuare questo come un programma per computer, avrete bisogno di due robot industriali :)

Per una più reale esempio del mondo, utilizzare il Ant colony optimization che dà ottimi risultati in breve tempo. Poiché è possibile specificare il numero di esecuzioni in questo algoritmo, è possibile decidere il tempo trascorso (ovvero il tempo di esecuzione dipende solo dal numero di nodi) che fornisce O (n) ma non un risultato perfetto garantito.

fonte

2009-11-09 14:35:41

Com'è che O (1)? –

Posso effettivamente pensare ad un algoritmo O (L), dove L è il numero di nodi nella soluzione corretta: quantum-bogo-shortest-path (http://en.wikipedia.org/wiki/Bogosort#Quantum_Bogosort) –

Is is O (1) se non si considera la fase di costruzione del grafico. – mouviciel

Esistono algoritmi più veloci di Dijkstra?

Sì. La domanda non è qualificata in modo da richiedere prestazioni migliori in tutti i casi, o anche nella maggior parte dei casi. Un algoritmo con prestazioni migliori in un singolo caso è sufficiente per stabilire una risposta affermativa.

Nonostante il numero generalmente maggiore di iterazioni richieste dal metodo Bellman-Ford over metodo di Dijkstra, in pratica il metodo Bellman-Ford può essere superiore a causa del sovraccarico minore per iterazione [dorato, B. 1976 . "Algoritmi a percorso più breve: un confronto," Ricerca operativa, vol. 44, pp. 1164-1168].

La citazione di cui sopra è di Dimitri P. Bertsekas (marzo 1992). "Un algoritmo di correzione delle etichette semplice e veloce per i percorsi più brevi" (PDF). Reti, vol. 23, pp. 703-709, 1993. http://www.mit.edu/people/dimitrib/SLF.pdf. Retrieved 2008-10-01.

In breve, la mia richiesta si basa sull'interpretazione di Golden di Bertsekas. Sia che la mia conclusione sia valida o meno, potresti trovare Bertsekas interessante per la sua classificazione dell'algoritmo Dijkstra come metodo con l'impostazione, in contrasto con l'etichetta che corregge i metodi.

fonte

2009-11-09 14:52:33

Ha chiesto specificamente soluzioni con runtime asintotico inferiore. –

OK, quindi considera questo come un lemma sulla strada per il risultato finale. –

In primo luogo, i risultati su ciò che è più veloce "in pratica" non sono rilevanti per ciò che ha * asintoticamente * una crescita migliore, perché i grafici incontrati nella pratica sono finiti e generalmente piccoli. Inoltre, più veloce nel 1976 non si traduce necessariamente più velocemente nel 2009. Per prima cosa, i grafici "in pratica" sono più grandi oggi - per fare un esempio esagerato, '200x^2' è quattro volte più veloce di' n^3' per n = 50, ma un quinto come lento per n = 1000. – ShreevatsaR

C'è sempre A *, ed è derivato come Gerarchico A * e A * JPS.

fonte

2012-07-01 01:48:37 Puppy

Penso che A * dipenda dal fatto che esiste una sorta di euristica significativa per dire quale potrebbe essere la via migliore. – mwfearnley

Esistono algoritmi più veloci di Dijkstra?

risposta

Problemi correlati