MODELOS DE REDES
INTRODUCCIÓN
El modelo de transporte y sus variantes es uno de los muchos problemas que se pueden representar y resolver como una red. Por ejemplo: a) Diseño de una red de tubería de gas natural mar adentro, que conecta fuentes del Golfo de México con un punto de entrega en tierra, con el objetivo de minimizar el costo de construcción de la red. b) Determinación de la ruta más corta que une dos ciudades en una red de caminos existentes. c) Determinación de la capacidad anual máxima en toneladas de una red de conductos de pasta aguada de carbón, que enlaza las minas carboneras de Wyoming con las plantas generadoras de electricidad de Houston. d) Determinación del programa de flujo de costo mínimo de los …ver más…

Ejemplo: A → B → C → A o representado como AB – BC – CA.

B
C
A
E
D
Un ciclo puede ser dirigido o no dirigido. Ejemplo: Para la siguiente red A → B → C → A es un ciclo no dirigido, puesto que la dirección del arco AC es opuesta a la de los arcos AB y BC. Por lo contrario D → E → D, es un ciclo dirigido (por contar con dos arcos distintos).

PROBLEMA DE LA RUTA MÁS CORTA
Su objetivo es encontrar la ruta más corta (la trayectoria con la mínima distancia total) del origen al destino.
El problema de la ruta más corta incluye un juego de nodos conectados donde sólo un nodo es considerado como el origen y sólo un nodo es considerado como el nodo destino. El objetivo es determinar un camino de conexiones que minimizan la distancia total del origen al destino. El problema se resuelve por el "algoritmo de etiquetado".

ALGORITMO DE DANTZING PARA EL PROBLEMA DE LA RUTA MÀS CORTA DE UNA RED
PASO 1. Construya una lista maestra, tabulando bajo cada nodo en orden ascendente según la distancia, las ramas o arcos que salen de él. Cada arco bajo un nodo dado se escribe con ése nodo como su nodo inicio. Omítase de la lista cualquier arco que tenga a la fuente como su segundo nodo o que tenga al destino como su primer nodo.
PASO 2. Marque con un asterisco a la fuente y asígnele el valor cero. Localice el arco más corto que coincida con la fuente y encierre en un círculo. Marque con un asterisco al segundo nodo de este arco y asigne a este nodo un valor