CAMINO ECONOMICO

A C
8
B

A
D

7 6 2 3
D
B B B B

C C C C

A A A A
D D D D

7 A
B

D
C

6
α B B
β
C C

A A
D D

8
4
8 A
B

D
C

9
B

A
D

A
B

D
C

4 A
B

D
C

B B
E
C

A
D

Sea el grafo G(E,U), donde E  es el conjunto finito de elementos vértices y U  es

el conjunto finito de arcos, que representan , por ejemplo:

- los vértices  intersección de rutas (ciudades o cruces)

- el número de arcos  longitud en kilómetros de cada tramo,

de modo tal que nuestro objetivo podría ser

determinar el camino más corto entre  y 

Si los números representaran el tiempo necesario para recorrerlo, teniendo en

cuenta las condiciones del tránsito, buscaríamos

determinar el camino más rápido entre  y 

Si los números representaran el costo en atravesar cada tramo, buscaríamos

determinar el camino de costo mínimo

Generalizando el problema, podemos decir que, si asociamos a cada arco (x i, xj) un

valor C(xi, xj), buscaríamos un camino  para el cual

F(  )=
( xi , x j )
 C ( xi , x j ) sea mínimo
Se puede simplificar la notación, haciendo:

(xi, xj) = u  i j

=> C(xi, xj) = C(u) o también C(xi, xj)= Cij

De modo tal que la función a optimizar (minimizar) sería:

F(  )=  C (u )
u

En síntesis, cuando la situación examinada puede representarse por un grafo

G=(E,U), el cual asociamos los valores Cij a los arcos,

El objetivo  será encontrar el camino para el cual la suma de los valores

asociados a los arcos sea mínima. Dicho camino será  0 , y la función económica
definida por F(  )=  C (i, j ) , tomará el valor óptimo F0-
( i , j )

Es decir:

F 0 (  )  F (  0 )  min

C
( i , j )
ij   Cij
( i , j ) 0
ALGORITMO DE FORD
Es un procedimiento fácil de mecanizar para redes con numerosos vértices.
Consiste en:

Primera Parte:

1) Se marca cada vértice Xi con un índice λi , tal que

  0
i   i  

2) Se busca un arco (xi, xj) para el cual

λj - λi > C(xi, xj)

3) Se reemplaza i por un i' , tal que:

i'  i  C ( xi , x j )
Queda claro que:

i'  i
i'  0 j  

4) Se repiten los pasos 2) y 3) hasta que ningún arco permita reducir más a
ninguno de los índices.

El último valor que se obtenga para  será la distancia mínima entre α y β.

Segunda Parte:

Esta segunda parte del algoritmo, permite detectar la ruta económica.

* Se busca un vértice XK1 , tal que:

  K 1  C ( X K 1 ,  )

Donde XK1 es el último vértice que se utilizó para determinar el 

*Luego, se busca un XK2 , tal que:

K1  K 2  C( X K 2 , X K1 )
*Prosiguiendo la búsqueda en forma análoga, llegaremos hasta

X Kn1  

El camino

 0  ( , X Kn , X Kn 1 ,............., X K 2 , X K 1 ,  )

es el camino económico entre α y β.

y la longitud de dicho camino

 es el valor óptimo de la función económica.

EJEMPLO

+∞ +∞
A 8 C
B

A
D

7 +∞ 3
6 2
A
B

D
C

D A
B

D
C

0 7 A
B

D
C

A
B

D
C

6
α A
B

D
C

β
B B

C C

A A

+∞
D D

8
4
8 A
B

D
C

9
B

A
D

A
B

D
C

4 A
B

D
C

B E
B

+∞ +∞
D

RESOLUCION POR ALGORITMO DE FORD

Primera Parte:

1) Asignamos valor cero al nodo origen o fuente y para el resto de los nodos el
valor +∞
2) Se busca un arco (xi, xj) para el cual

λj - λi > C(xi, xj)

En nuestro caso: λA - α = ∞ > 7 =>  A' = λα + 7

λB - α = ∞ > 8 => B' = λα + 8

Del mismo modo:

λD - λA =∞ - 7> 6 => D' = 7 + 6= 13

Ahora bien, a D puede llegarse a través de B, entonces

λD – λB = 13 - 8= 5 > 4 => D' = 4 + 8= 12

 para decidir, se toma el menor valor.

Continuando el análisis, resultará:

 7
14
+∞ 15
A 8 C +∞
B
8
C

A
D

12
7 13 3
6 2 17
0 A
B

D
C
+∞ A
B

D
C

18
7 6
0 β +∞
B B

C C

A A
D D

α A
B

D
C

D A
B

D
C

8
4 A
B

D
C

8 A
B

D
C

9
B

A
D

A
B

D
C

4 A
B

D
C

B E
B

+∞ +∞
D

8 8

Así, cuando para ningún arco se cumpla la condición λj - λi > C(xi, xj), el proceso
termina.
0> podemos decir que el valor de la función objetivo es:

F(  0 )= 
( xi , x j )
C ( xi , x j ) = 17
Segunda Parte: Camino Optimo

Para identificar el grafo parcial (es decir el que se obtiene suprimiendo arcos) que
nos identifica el camino óptimo, lo definimos como aquel en el cual los arcos
satisfacen la siguiente igualdad:

λj - λj = C(xi, xj)

Partiendo del grafo resultante de la Primera Parte:

7 14
A 8 C
B

A
D

7 12 3
6 2
A
B

D
C

D A
B

D
C

0 7 A
B

D
C

A
B

D
C

6
α A
B

D
C

β
B B

C C

A A
D D

8 17
4
8 A
B

D
C

9
B

A
D

A
B

D
C

4 A
B

D
C

B E
B

A
D

8 12

Analizamos los tramos del grafo, comenzando con los que llegan al nodo destino:

* λβ - λC = 17 – 14 = 3 = C(C, β)=3 => arco perteneciente al camino óptimo

λβ - λE = 17 – 12 = 5 < C(E, β)=9

λβ - λD = 17 – 12 = 5 < C(D, β)=6

* λC - λA = 14 – 7 = 7 < C(A, C)=8

λC - λD = 14 – 12 = 2 = C(E, β)=2 => arco perteneciente al camino óptimo

* λE - λD = 12 – 12 = 0 < C(D, E)=8

λE - λB = 12 – 8 = 4 = C(B, E)=4 => arco perteneciente al camino óptimo

* λD - λA = 12 – 7 = 5 < C(A, D)=6

λD - λB = 12 – 8 = 4 = C(B, D)=4 => arco perteneciente al camino óptimo

* λB - λA = 8 – 7 = 1 < C(A, B)=7

λB - λα = 8 – 0 = 8 = C(α, B)=8 => arco perteneciente al camino óptimo

* λA - λα = 7 – 0 = 7 = C(α, A)=7 => arco perteneciente al camino óptimo

 el grafo parcial que nos da el camino óptimo es:

A C
8
B

A
D

7 6 2 3
D
B B B B

C C C C

A A A A
D D D D

7 A
B

D
C

6
α β
B B

C C

A A
D D

8
4
8 A
B

D
C

9
B

A
D

A
B

D
C

4 A
B

D
C

B E
B

A
D

 = (α, B, D, C, β) Fo = 8+ 4+ 2+ 3= 17

Esta metodología no sólo nos suministra el camino óptimo entre α y β, sino el

óptimo entre α y cada uno de los vértices.
 RESOLUCION POR TABLA

A C
8
B

A
D

7 6 2 3
D
B B B B

C C C C

A A A A
D D D D

7 A
B

D
C

6
α β
B B

C C

A A
D D

8
4
8 A
B

D
C

9
B

A
D

A
B

D
C

4 A
B

D
C

B E
B

A
D

Construimos una tabla donde en cada columna colocamos los arcos que tienen
origen el mismo vértice, ordenándolos en forma creciente según el valor
correspondiente.

α A B C D E β
αA= 7 AD= 6 BE= 4 CD= 2 DC= 2 EB= 4 βC = 3
αB= 8 AB= 7 BD= 4 Cβ = 3 DB= 4 ED= 8 βD = 6
Aα = 7 BA= 7 CA = 8 DA= 6 Eβ = 9 βE = 9
AC= 8 Bα = 8 Dβ = 6
DE= 8

1.- Le damos al vértice de entrada a la red ( en nuestro caso α), el valor cero y lo
colocamos encima de la columna.
2.- Eliminamos todos los arcos que tengan dicho vértice como destino
3.- Seleccionamos el arco αA, pues nos dá la menor suma 0+7=7 y lo recuadramos.
0
α A B C D E β
αA= 7 AD= 6 BE= 4 CD= 2 DC= 2 EB= 4 βC = 3
αB= 8 AB= 7 BD= 4 Cβ = 3 DB= 4 ED= 8 βD = 6
Aα = 7 BA= 7 CA = 8 DA= 6 Eβ = 9 βE = 9
AC= 8 Bα = 8 Dβ = 6
DE= 8
Repetimos el procedimiento, es decir:
Sobre A colocamos el valor 7 y eliminamos los arcos con destino A

0 7
α A B C D E β
αA= 7 AD= 6 BE= 4 CD= 2 DC= 2 EB= 4 βC = 3
αB= 8 AB= 7 BD= 4 Cβ = 3 DB= 4 ED= 8 βD = 6
Aα = 7 BA= 7 CA = 8 DA= 6 Eβ = 9 βE = 9
AC= 8 Bα = 8 Dβ = 6
DE= 8

Ahora hay 2 columnas a considerar, es decor dps vértices:

0 + c(α,B) = 0 + 8 = 8
7 + c( A,D) = 7 + 6= 13

Luego, la suma menor es la asociada al arco (α,B) =>

-se recuadra (α,B) ,
-se coloca el valor de la suma sobre la columna B,
-se eliminan los arcos con destino B.

0 7 8
α A B C D E β
αA= 7 AD= 6 BE= 4 CD= 2 DC= 2 EB= 4 βC = 3
αB= 8 AB= 7 BD= 4 Cβ = 3 DB= 4 ED= 8 βD = 6
Aα = 7 BA= 7 CA = 8 DA= 6 Eβ = 9 βE = 9
AC= 8 Bα = 8 Dβ = 6
DE= 8

A esta altura, hemos agotado las posibilidades de la columna α, => debemos

analizar las columnas A y B

7 + c(A,D) = 7 + 6 = 13
8 + c( B,E) = 8 + 4 = 12
Luego, la suma menor es la asociada al arco (B,E) =>
-se recuadra (B,E) ,
-se coloca el valor de la suma sobre la columna E,
-se eliminan los arcos con destino E.

0 7 8 12
α A B C D E β
αA= 7 AD= 6 BE= 4 CD= 2 DC= 2 EB= 4 βC = 3
αB= 8 AB= 7 BD= 4 Cβ = 3 DB= 4 ED= 8 βD = 6
Aα = 7 BA= 7 CA = 8 DA= 6 Eβ = 9 βE = 9
AC= 8 Bα = 8 Dβ = 6
DE= 8

Analizamos luego las columnas A, B y E

7 + c(A,D) = 7 + 6 = 13
8 + c( B,D) = 8 + 4 = 12
12+ c(E,D) = 12 + 8 = 20

Luego, la suma menor es la asociada al arco (B,D) =>

-se recuadra (B,D) ,
-se coloca el valor de la suma sobre la columna D,
-se eliminan los arcos con destino D.

0 7 8 12 12
α A B C D E β
αA= 7 AD= 6 BE= 4 CD= 2 DC= 2 EB= 4 βC = 3
αB= 8 AB= 7 BD= 4 Cβ = 3 DB= 4 ED= 8 βD = 6
Aα = 7 BA= 7 CA = 8 DA= 6 Eβ = 9 βE = 9
AC= 8 Bα = 8 Dβ = 6
DE= 8

La columna B está agotada, entonces quedan por analizar las columnas A, D y E

7 + c(A,D) = 7 + 8 = 15
12 + c( D,C) = 12 + 2 = 14
12+ c(E,β) = 12 + 8 = 21

Luego, la suma menor es la asociada al arco (A,C) =>

-se recuadra (A,C) ,
-se coloca el valor de la suma sobre la columna C,
-se eliminan los arcos con destino C.

0 7 8 14 12 12 17
α A B C D E β
αA= 7 AD= 6 BE= 4 CD= 2 DC= 2 EB= 4 βC = 3
αB= 8 AB= 7 BD= 4 Cβ = 3 DB= 4 ED= 8 βD = 6
Aα = 7 BA= 7 CA = 8 DA= 6 Eβ = 9 βE = 9
AC= 8 Bα = 8 Dβ = 6
DE= 8

Ahora debemos analizar las columnas C, D y E

14 + c( C,β) = 14 + 3 = 17
12+ c(E,β) = 12 + 8 = 21
12 + c(D,β) = 12 +6 = 18

Luego, la suma menor es la asociada al arco (C,β) =>

-se recuadra (C,β) ,
-se coloca el valor de la suma sobre la columna β,
Así, los arcos recuadrados permiten definirle camino óptimo y los números sobre
cada vértice nos dan las distancias mínimas.

A C

7 2 3
D
B

A
D

B B B

C C C

A A A
D D D

A
D

α β
B

A
D

4
B

A
D

8
B

A
D

A
B

D
C

4
B E
B

A
D

 = (α, B, D, C, β) Fo = 8+ 4+ 2+ 3= 17