Page 86 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
P. 86
INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
El tiempo para ejecutar el algoritmo Prim es del (n ) donde n es el número de nodos. La matriz
2
costo del ejemplo anterior junto con una simulación de los valores históricos del vector NEAR quedan
como se observa en la tabla 3.1.
Tabla 3.1. Simulación de la estrategia Prim utilizando el algoritmo 3.3 para la figura 3.2
la ruta MáS corta a partIr de uN orIgeN (SINgle Source SHorteSt patHS)
Los grafos pueden ser utilizados para representar carreteras donde los vértices simbolizan ciudades
y los segmentos que las unen son la carretera. Los segmentos pueden tener asignados pesos que
marcan una distancia entre dos ciudades conectadas.
La distancia de un trayecto es definida por la suma del peso de los segmentos. El vértice de inicio
se definirá como el origen y el último como el destino. El problema para considerar se basará en una
gráfica dirigida G = (V, E), una función de peso c(e) para los segmentos de G y un vértice origen v .
0
El problema es determinar el trayecto más corto de v a todos los demás vértices de G. Se asume
0
que todos los pesos son positivos.
Ejemplo: Considere la gráfica dirigida de la figura 3.4. El número de trayectos también es el número
de pesos. Si v es el vértice de origen, entonces el trayecto más corto desde v a v es v v v v La
0 0 1 0 2 3 1.
distancia del trayecto es 10 + 15 + 20 = 45. En este caso, recorrer tres caminos es más económico
que transitar en forma directa v v , el cual tiene un costo de 50.
0 1 ,
80
