Perché usare l'algoritmo di Dijkstra se ricerca in ampiezza (BFS) può fare la stessa cosa più veloce?

Question

Sia può essere usato per trovare il percorso più breve da un'unica fonte. BFS viene eseguito in O(E+V), mentre corre di Dijkstra in O((V+E)*log(V)).

Dijkstra Inoltre, ho visto usato un po 'come in protocolli di routing.

Quindi, il motivo per cui l'algoritmo di Dijkstra uso se BFS può fare la stessa cosa più veloce?

Answer 1

Dijkstra permette di assegnare distanze diverse 1 per ogni passaggio. Ad esempio, nel passaggio dei distanze (o pesi) potrebbe essere assegnato dalla velocità, costi, preferenze, ecc L'algoritmo quindi offre il percorso più breve dalla sorgente a ogni nodo del grafo attraversato.

BFS Nel frattempo fondamentalmente solo espande la ricerca di un “passo” (link, bordo, qualunque cosa si voglia chiamare nell'applicazione) su ogni iterazione, che succede ad avere l'effetto di trovare il più piccolo numero di passi che ci vuole per arrivare a un dato nodo dalla sorgente ( “root”).

Answer 2

Se si considera siti web di viaggi, algoritmo di questi l'uso di Dijkstra a causa di pesi (distanze) su nodi.

Se si prenderà in considerazione la stessa distanza tra tutti i nodi, quindi BFS è la scelta migliore.

Per esempio, si consideri A -> (B, C) -> (F) con il bordo pesi dati da A->B = 10, A->C = 20, B->F = C->F = 5.

Qui, se applichiamo BFS, la risposta sarà ABF o ACF, in quanto entrambi sono percorsi più brevi (rispetto al numero di spigoli), ma se applichiamo Dijstra di, la risposta sarà ABF solo perché considera i pesi sul percorso collegato.

Answer 3

L'algoritmo di Dijkstra

• Come BFS per grafi pesati.
• Se tutti i costi sono uguali, Dijkstra = BFS

Fonte: https://cs.stanford.edu/people/abisee/gs .pdf

Answer 4

Dal punto di vista dell'attuazione, l'algoritmo di Dijkstra potrebbe essere implementato esattamente come un BFS scambiando il queue con un priority queue.

Fonte: entra descrizione Link qui