differenza tra l'algoritmo di Bellman Ford e Dijkstra

Question

2   1 
1----------2---------4 
|   |   | 
|3   |3  |1 
| 6  |   | 
3---------5 --------- 

Ok, quindi questo è il grafico. Il mio nodo di origine è 1 e il nodo di destinazione è 5

La mia domanda è.

Entrambi gli algoritmi forniscono lo stesso risultato oppure no? Ovvero, restituiranno entrambi 1->2->4->5? (Tranne che i pesi negativi non sono ammessi in Dijkstra)

Grazie in anticipo per l'aiuto.

Answer 1

L'algoritmo di Bellman-Ford è un algoritmo di percorso più breve a sorgente singola, che consente il peso del bordo negativo e può rilevare cicli negativi in ​​un grafico.

L'algoritmo dijkstra è anche un altro algoritmo di percorso più breve a sorgente singola. Tuttavia, il peso di tutti i bordi deve essere non negativo.

Per il tuo caso, per quanto riguarda il costo totale, non ci saranno differenze, poiché i bordi del grafico hanno un peso non negativo. Tuttavia, l'algoritmo di Dijkstra viene solitamente utilizzato, poiché l'implementazione tipica con l'heap binario ha una complessità temporale pari a Theta((|E|+|V|)log|V|), mentre l'algoritmo di Bellman-Ford ha la complessità O(|V||E|).

Se esistono più di 1 percorso con un costo minimo, il percorso effettivo restituito dipende dall'implementazione (anche per lo stesso algoritmo).

Answer 2

I vertici nell'algoritmo di Dijkstra contengono l'intera informazione di una rete. Non esiste una cosa del genere che ogni vertice si preoccupi solo di se stesso e dei suoi vicini. D'altra parte, l'algoritmo di Bellman-Ford nodescontain solo le informazioni che sono correlate. Questa informazione consente a quel nodo solo di sapere quali nodi vicini possono connettersi e il nodo da cui proviene la relazione, a vicenda. L'algoritmo di Dijkstra è più veloce dell'algoritmo di Bellman-Ford, tuttavia il secondo algoritmo può essere più utile per risolvere alcuni problemi, come i pesi negativi dei percorsi.