Page 88 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

a u, el vértice u viene a ser miembro de S. En este punto la dimensión del trayecto
más corto iniciando en v irá en los vértices localizados en S y terminando en w
0
no en S puede decrecer. Esto es, el valor de la distancia DIST(w) puede cambiar.
Si cambia, se debe a que existe un trayecto más corto iniciando en v y posterior-
0
mente va a u y entonces a w. Los vértices intermedios de v a u y de u a w deben
0,
estar todos en S. Además, el trayecto v a u debe ser el más corto; de otra manera,
0
DIST(w) no está definido en forma apropiada. También, el trayecto u a w puede no
contener vértices intermedios.

Las observaciones arriba indicadas crean un algoritmo simple, el cual fue desarrollado por Dijkstra
(este algoritmo es la base para el ruteo en internet). De hecho, solo determina la magnitud de la tra-
yectoria del vértice v a todos los vértices en G.
0
Se asume que los n vértices en G se numeran de 1 a n. El conjunto se mantiene S con un arreglo
con S(i) = 0 si el vértice i no se encuentra en S y S(i) = 1 si pertenece a S. Se asume que la gráfica
se representa por una matriz de costos. Horowitz y Sahni (1978) muestran el algoritmo general 3.4
en formato pseudocódigo.

Algoritmo 3.4. Método de Dijkstra para la ruta más corta

82