Modelo ciclico

MODELO DIJKSTRA O CÍCLICO.

Este algoritmo permite tantas veces sea necesario revalorar un nodo. Cuando resulta evidente que se ha alcanzado la distancia más corta a un nodo, este se excluye de cualquier consideración posterior. El proceso termina cuando sea evaluado el nodo destino.

Éste algoritmo usa dos temas de etiqueta: temporal y permanente. Ambas usan el siguiente formato:

d: distancia más corta disponible hasta el momento.

n: es el nodo inmediato precedente al cuál la distancia es igual a d.

El algoritmo comienza con el nodo fuente que lleva la etiqueta permanente [0,-] luego consideramos todos los nodos que se pueden alcanzar directamente desde el nodo fuente y determinamos sus etiquetas asociadas. Las etiquetas recién creadas se designan como temporales. La siguiente etiqueta permanente se selecciona como aquella de todas las etiquetas temporales que tengan la menor d en la etiqueta (los empates se rompen arbitrariamente). El proceso se repite para el último nodo que se ha designado permanente.

En tal caso, una etiqueta temporal de un nodo se puede cambiar solo si la nueva etiqueta da una distancia de menor.

Todo nodo de una red fuertemente conexa puede estar en uno de los tres estados siguientes:

1. Sin etiqueta
2. Etiquetado y no explorado
3. Etiquetado y explorado

El objetivo del algoritmo es determinar el camino mínimo desde el nodo origen a cualquier nodo de la red mediante el etiquetamiento de los nodos como parejas ordenadas de dos elementos. El primer elemento de la etiqueta describe el valor del camino mínimo desde el nodo origen hasta el nodo en cuestión.

El segundo nodo de la etiqueta describe el nodo desde el cuál precede.

PROCEDIMIENTO

1. Se define el nodo origen cuya etiqueta es [0,-] (el nodo origen se denota con S)
2. Se consideran los nodos vecinos o adyacentes y se les etiqueta provisionalmente con el valor del nodo inicial
3. Se selecciona el nodo vecino etiquetado provisionalmente con la menos primer componente. La etiqueta provisional del nodo seleccionado pasa a ser etiqueta permanente. Se etiqueta provisionalmente los nodos adyacentes o vecinos a este nodo, siendo la primera componente la suma de los valores de los arcos entre el nodo origen y el nodo que se está etiquetando mientras que la segunda componente muestra el nodo del que se proviene.
4. De los nodos que tienen etiqueta provisional, se vuelve a seleccionar aquel nodo cuyo primer componente sea la menor. Se repite el paso tres hasta alcanzar el último nodo de la red de tal manera que todas las etiquetas provisionales se hayan transformado en etiquetas permanentes.

Ejercicio.

METODO MATRICIAL= METODO GRAFICO

Sea j la capacidad del arco (i, j) en la dirección de  i a j sea C= { Cij } la matriz de capacidades originales de los arcos de una red fuertemente conexa con n nodos, la matriz C es una matriz cuadrada de orden n

El fluo máximo que pasa por la red cumple:

FM= <= min {∑j  Cij; ∑ Ci+}

El método matricial para determinar el flujo máximo está dividido en tres etapas:

1. DETERMINACIÓN DEL FLUJO EN UNA TRAYECTORIA:

• Paso 1: construye la matriz de capacidades de la red (los nodos como renglones son los nodos iniciales de los arcos y los nodos como columnas son los nodos terminales de los arcos)
• Paso 2: determina una trayectoria desde el nodo de la red S hasta el nodo destino T con capacidades (>0) en los arcos que la forman, en la dirección de S a T y se marcan en la matriz C las capacidades de  Cij con supra índice negativo Cij -  y con  un supra índice positivo a las capacidades de los mismos arcos pero en dirección opuesta Cij +
• Paso 3: se calcula la cantidad máxima de flujo θ que puede viajar a través de la trayectoria seleccionada como: θ= min { Cij - } Donde Cij es igual a las capacidades de los arcos que forman la trayectoria seleccionada de S a T.

1. CONSERVACIÓN DEL FLUJO

• Paso 4: se resta el valor de θ a las capacidades marcadas como Cij -  y se suma θ a las capacidades de los arcos marcados como Cij +. A la matriz que se obtiene  se le denomina como la matriz C*={ Cij * }
• Paso 5: regresa al paso 2 hasta que ya no sea posible encontrar una trayectoria con capacidades estrictamente positivas en los arcos que la forman

1. DISTRIBUCIÓN DEL FLUJO MÁXIMO

• Paso 6: se determina la matriz X={Xij} de distribución del flujo máximo, como Xij={cij-cij* sí Cij>Cij* y; Cero sí Cij<= Cij* } dónde: C{Cij} es la matriz de capacidades y C*{Cij*} es la última matriz modificada. Y el flujo máximo =2 θi=2Xij=2Xji

...