algoritmo di Dijkstra

todo

• cosa risolve
• idea
• problema con i pesi negativi
• esempio in cui sbaglia
• alternativa (costosa, perché diventa n volte più lento) con bfs e nodi dummy

Implementazioni

Con liste

L’implementazione con le liste costa $O(n^2)$.

Con heap

L’implementazione con l’heap costa $O((n+m)\log n)$