Entrambi possono essere utilizzati per trovare il percorso più breve da una singola fonte. BFS gira in O (E + V), mentre Dijkstra corre in O ((V + E) * log (V)).Perché usare Algorithm di Dijkstra se Breadth First Search (BFS) può fare la stessa cosa più velocemente?
Inoltre, ho visto Dijkstra utilizzato molto come nei protocolli di routing.
Quindi, perché utilizzare l'algoritmo di Dijkstra se BFS può fare la stessa cosa più velocemente?
Dijkstra consente di assegnare distanze diverse da 1 per ogni passo. Ad esempio, nell'instradamento le distanze (oi pesi) potrebbero essere assegnate dalla velocità, dal costo, dalle preferenze, ecc. L'algoritmo quindi fornisce il percorso più breve dalla sorgente a ogni nodo nel grafico attraversato.
Nel frattempo BFS 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 passaggi serve per raggiungere un determinato nodo dalla tua origine ("root").
Se si considerano siti Web di viaggi, questi utilizzano l'algoritmo di Dijkstra a causa di pesi (distanze) sui nodi.
Se si considera la stessa distanza tra tutti i nodi, quindi BFS è la scelta migliore.
Ad 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, la risposta sarà ABF solo perché considera i pesi sul percorso connesso.
Entrambi producono gli stessi risultati, ovvero un percorso tra due vertici, ma solo dijkstra garantirà il percorso più breve. – Edwin
Vedere la risposta accettata, secondo commento. Un modo molto carino di spiegare perché la complessità computazionale è diversa: https://stackoverflow.com/questions/25449781/what-is-difference-between-bfs-and-dijkstras-algorithms-when-looking-for-shorte – jmcarter9t