Philippe Picard, le 16 mars
2009
Page ‹N°›
Routage IP: 2 familles
d’algorithmes
Si N désigne le nombre
de noeuds du graphe et A le nombre d'arcs:
•L'algorithme de Dijkstra est en O((N+A)xlogA, c’est-à-dire O(N2xlogN) pour un graphe dense
•L’algorithme de Ford Bellmann est en O(NxA), c.a.d O(N3) pour un graphe dense
Ces algorithmes sont dits gloutons (optimisation par étapes)