Il existe une version spécialisée de cet algorithme, connue sous le nom d’algorithme de Sedgewick-Vitter, basée sur un tas. Par rapport à l’algorithme de Dijkstra, le tas H est classé selon les valeurs de F au lieu de D. L’algorithme est alors bien plus rapide en moyenne : les sommets fixés avant t forment un fuseau plus ou moins étroit de s à t et ne représentent qu’une petite partie des sommets du graphe.
[^] # Re: Petite reflexion
Posté par nomorepost . En réponse au journal OpenStreetMap dans le Monde. Évalué à 2.
! .doc inside
http://www.etnoka.fr/redirect/2581/qualified/attachment/9476(...)
Il existe une version spécialisée de cet algorithme, connue sous le nom d’algorithme de Sedgewick-Vitter, basée sur un tas. Par rapport à l’algorithme de Dijkstra, le tas H est classé selon les valeurs de F au lieu de D. L’algorithme est alors bien plus rapide en moyenne : les sommets fixés avant t forment un fuseau plus ou moins étroit de s à t et ne représentent qu’une petite partie des sommets du graphe.
Algo :
algorithme de SEDGEWICK-VITTER
INIT D à + \ ;
D( s ) = 0 ;
F( t ) = H( t ) ;
CLEAR ( Tas ) ;
INSERT ( Tas , F , s ) ;
REPEAT
TAKE_MIN ( Tas , F , i ) ;
FOR k = 1 TO NB_SUCC ( i )
ARC_SUIVANT ( i , j , d , k ) ;
IF ( D( i ) + d < D( j ) ) THEN
D( j ) = D( i ) + d ;
F( j ) = D( j ) + H( j ) ;
PRED ( j ) = i ;
IF not INSIDE( Tas , j ) THEN
INSERT( Tas , F , j ) ;
ELSE
MOVE_UP( Tas , F , j ) ;
END IF
END IF
END FOR
UNTIL ( EMPTY ( Tas ) OR i = t ) .