Algoritmos de flujo máximo

EN ALGUNOS PROBLEMAS DE OPTIMIZACIÓN PUEDE SER ÚTIL REPRESENTAR EL PROBLEMA A TRAVÉS DE UNA GRÁFICA: ruteo de vehículos, distribución deproducto, programa de actividades en un proyecto, redes de comunicación, etc.
MODELOS DE REDES: algoritmos especiales.
ALGORITMO DE DIJKTRA’S:
Lamarca del nodo j es de la forma [uj,i]=[ui+cij,i], donde ui es la distancia mas corta del nodo origen al nodo i con marca Permanente y cij el costodel arco (i,j). Los nodos que no pueden alcanzarse directamente a partir de un nodo con marca Permanente tendrán marca Temporal igual a .

UnCamino o Ruta del nodo i al nodo j es una secuencia de arcos que unen el nodo i con el nodo j: (i,i1), (i1,i2), (i2,i3),...,(ik,j). Ruta de karcos.
Un Ciclo es un camino que une un nodo consigo mismo:(i,i1), (i1,i2), (i2,i3),...,(ik,i)
UNA SUBGRÁFICA G’=(N’,A’) DE UNA GRÁFICA G=(N,A) esun conjunto de nodos y arcos de G: N’ N y G’  G.
UNA GRÁFICA G=(N,A) ES CONEXA si para cada par de nodos i,j  N existe un camino que conecteel nodo i con el nodo j.

Sea i=1 el nodo origen
Paso 0: marcar el nodo origen con [0,0], i=1, P={1}, T={2,3,…n}.
Paso 1:  jT marcar[uj,,i]=[ui+cij,i]. Si el nodo j tiene marca temporal [uj,k] y ui+cij.

Los problemas de transporte, transbordo, camino mas corto, flujo máximo,redde proyectos(CPM) son casos especiales del modelo de FLUJO DE COSTO MÍNIMO EN UNA RED y pueden resolverse con una forma especial del Simplex .