Vicerrectoría General
Dirección Nacional de Servicios Académicos Virtuales
Dentro de las aplicaciones clásicas y fundamentales se encuentra el estudio de redes. En este campo se han desarrollado técnicas como son Cálculo del Flujo Máximo y Cálculo del Costo Mínimo; en ambos casos se trata de optimización en redes.
Para el Flujo máximo existen 3 algoritmos conocidos:
METODO DE CORTES
METODO DE GRAFICO AUXILIAR
METODO DE FORD - FULKERSON
Para el Costo Mínimo existen 2 algoritmos conocidos:
METODO DE GRAFICOS DIRIGIDOS
METODO DE DIJKSTRA
7.3.1 Algoritmo De Dijkstra
Este algoritmo usado para determinar el costo mínimo, es el más implementado en ciertos dispositivos de Hardware. Se encarga de determinar las rutas con el menor costo, desde un nodo origen hacia todos los otros nodos de un grafo.
El algoritmo va pasando por diferentes estados. En el estado K, las rutas más cortas a los K nodos más cercanos han sido determinadas y estos nodos están dentro de un grupo denominado M. En el estado K + 1, un nodo que no está en M y que tiene la ruta más corta desde el nodo origen es incluido en M.
Al final todos los nodos estaran en M, y sus rutas desde el origen habran sido determinadas.
El algoritmo puede ser formalmente descrito como sigue:
N = número de nodos en el grafo( red ).
s = nodo fuente
M = grupo de nodos que han sido incorporados por el algoritmo.
dij= Costo del enlace desde el nodo i al nodo j; dii
= 0 y dij =
si los dos nodos no están directamente conectados;
dij>= 0 si los dos nodos están directamente
conectados.
Dn= costo de la ruta con el menor costo, desde el nodo
s al nodo n.
El algoritmo tiene tres pasos; los pasos 2 y 3 son repetidos hasta que M = N. Es decir tales pasos son repetidos hasta que las rutas finales han sido asignadas a todos los nodos de la red:
1. Inicializar:
M = {s}
// Al grupo de nodos M solo se incorpora el nodo origen.
Dn = dsn para n >s
// Los costos de las rutas iniciales hacia los nodos vecinos son
simplemente los costos del enlace.
2. Encontrar el nodo vecino que no está
en M y que tiene el enlace con menor costo desde el nodo s. El nodo
encontrado se incorpora a M.
Encontrar w M tal que Dw = min { Dj } para j M
Insertar w a M.
3. Actualizar las rutas con el costo mínimo:
Dn = min[Dn, Dw + dwm] para todo j M
Sí el último término es el mínimo, la
ruta de s a n es ahora la uta desde s a w concatenada con el enlace
que va de w a n.
Cada iteración de los pasos 2 y 3 coloca un nuevo nodo en M y define la ruta con costo mínimo desde s hasta ese nodo. Esa ruta solo pasa a través de nodos que están en M.
Figura 7.22 Dígrafo
La siguiente tabla muestra el resultado de aplicar el algoritmo sobre el grafo de la figura 7.22, usando s =1 como nodo de origen.
La siguiente figura muestra el resultado de cada iteración:
Figura 7.23 Algoritmo de Dijkstra
