Algo Dijkstra

• \(d(i)\) cout min d'un chemin en passent par les noeuds déja visités

• \(Ns\) ensemble des noeuds visités

• \(v\) le noeuds ajouté (le plus proche parmi les invisités)

• loop :

  • \(v\) : element minimise d(v)
  • \(Ns\) := NS U {v}

\(\mathcal{O}(|N^2|)\)