BELLMAN-FORD
Jorge Mondragón
Leonardo Herrera
Cristian Fernández
DESCRIPCIÓN DEL PROBLEMA
El algoritmo de Bellman-Ford genera el camino más
corto en un grafo dirigido ponderado (en el que el
peso de alguna de las aristas puede ser negativo).
El algoritmo de Dijkstra resuelve este mismo problema
en un tiempo menor, pero requiere que los pesos de
las aristas no sean negativos. Por lo que el algoritmo
Bellman-Ford normalmente se utiliza cuando hay
aristas
con
peso
negativo
Si el grafo contiene un ciclo de coste negativo, el
algoritmo lo detectará pero no encontrará el camino
más corto que no repite ningún vértice, la complejidad
de este problema es NP-completo.
DEFINICIÓN DEL ALGORITMO
• El algoritmo de Bellman-Ford genera el camino más
corto en un Grafo dirigido ponderado ( en el que el
peso de alguna de las aristas puede ser negativo).
• Este Algoritmo fue
desarrollado por Richard
Bellman, Samuel End y
Lester Ford.
CARACTERISTICAS Y
COMPLEJIDAD
COMPUTACIONAL
• El algoritmo de Dijkstra resuelve este mismo problema
en un tiempo menor, pero requiere que los pesos de
las aristas no sean negativos. Por lo que el Algoritmo
Bellman-Ford normalmente se utiliza cuando hay
aristas con peso negativo.
• La complejidad computacional de este problema es
complejidad NP-Completo.
EXPLICACIÓN DEL ALGORITMO
• En el paso 0, inicializamos todas las distancias o
costos
mínimos
a
infinito.
En el paso 1, actualizamos el paso anterior, aplicando
las fórmulas. En este caso ponemos la distancia de
los nodos que tienen accesos directos al vértice 1, y
se la sumamos a la distancia mínima acumulada que
hay hasta el vértice oportuno. Aquí esta distancia
acumulada sería 0 para 1, debido que sería la
distancia a él mismo, e infinito para el resto porque no
han sido analizados todavía
EXPLICACIÓN DEL
ALGORITMO
• En el paso 2, al saber ya una distancia mínima
acumulada desde los nodos 2 y 3 hasta 1,
podemos actualizar las distancias mínimas de los
nodos
4
y
5.
En los pasos sucesivos, se van actualizando las
distancias mínimas acumuladas (D) de los
distintos vértices hasta 1, y se van utilizando en
los pasos siguientes para optimizar el camino
mínimo. El final del algoritmo se da cuando no hay
ningún cambio de un paso a otro, cuando ya no se
puede encontrar un camino más corto.
ANALISIS DEL ALGORITMO
•Grafo Inicial.
•El
objetivo
del
Algoritmo
es
encontrar el camino
mínimo desde todos
los nodos al vértice 1.
ANALISIS DEL ALGORITMO
EJEMPLO ( REALIZACIÓN DEL
ALGORITMO)
EJEMPLO (GRAFO FINAL)
*
Resultado
del
camino
mínimo
desde todos los
nodos al vértice 1.
APLICACIONES DEL
ALGORITMO
• Una variante distribuida del Algoritmo del BellmanFord se usa en protocolos de encaminamiento
basados en vector de distancias.
• En el mundo de las redes (comunicaciones) el
protocolo de encaminamiento de información (RIP).
http://neo.lcc.uma.es/evirtual/cdd/applets/BellmanFord
/Example3.html
u
v
5
Lista de Arcos
-2
6
z
-4
8
7
-3
7
2
x
9
y
(u,v)
(u,x)
(u,y)
(v,u)
(x,v)
(x,y)
(y,v)
(y,z)
(z,u)
(z,x)
Paso 0.0
V
[
]
=
{
u v
x
y
z
}
d
[
]
=
{
_
_
_
_
_
}
P
[
]
=
{
_
_
_
_
_
}
Encontrar el camino más corto del
Vértice z a cada uno de los otros
Vértices.
u
5

-2
6
z
v
Lista de Arcos

(u,v)
(u,x)
(u,y)
(v,u)
(x,v)
(x,y)
(y,v)
(y,z)
(z,u)
(z,x)
-4
0
8
7
-3
7
x
2

9
y

Paso 0.1
V
[
]
=
{
u v
x
y
z
}
d
[
]
=
{
    0
}
P
[
]
=
{
}
Inicializar los vectores d y P.
u
v
5


-2
6
z
Lista de Arcos
-4
0
8
7
-3
7
x
2

y
9
Paso 1.1
V
[
]
=
{
u v
x
y
z
}
d
[
]
=
{
    0
}
P
[
]
=
{
}

(u,v)
(u,x)
(u,y)
(v,u)
(x,v)
(x,y)
(y,v)
(y,z)
(z,u)
(z,x)
Aplicar Relax al Arco (u,v)
Pregunta: ¿ d[v] > d[u] + w( u , v ) ?
Respuesta:
Proceso:
NO
No se hace nada.
u
v
5


-2
6
z
Lista de Arcos
-4
0
8
7
-3
7
x
2

y
9
Paso 1.2
V
[
]
=
{
u v
x
y
z
}
d
[
]
=
{
    0
}
P
[
]
=
{
}

(u,v)
(u,x) 
(u,y)
(v,u)
(x,v)
(x,y)
(y,v)
(y,z)
(z,u)
(z,x)
Aplicar Relax al Arco (u,x)
Pregunta: ¿ d[x] > d[u] + w( u , x ) ?
Respuesta:
Proceso:
NO
No se hace nada.
u
v
5


-2
6
z
Lista de Arcos
-4
0
8
7
-3
7
x
2

y
9
Paso 1.3
V
[
]
=
{
u v
x
y
z
}
d
[
]
=
{
    0
}
P
[
]
=
{
}

(u,v)
(u,x)
(u,y) 
(v,u)
(x,v)
(x,y)
(y,v)
(y,z)
(z,u)
(z,x)
Aplicar Relax al Arco (u,y)
Pregunta: ¿ d[y] > d[u] + w( u , y ) ?
Respuesta:
Proceso:
NO
No se hace nada.
u
v
5


-2
6
z
Lista de Arcos
-4
0
8
7
-3
7
x
2

y
9
Paso 1.4
V
[
]
=
{
u v
x
y
z
}
d
[
]
=
{
    0
}
P
[
]
=
{
}

(u,v)
(u,x)
(u,y)
(v,u) 
(x,v)
(x,y)
(y,v)
(y,z)
(z,u)
(z,x)
Aplicar Relax al Arco (v,u)
Pregunta: ¿ d[u] > d[v] + w( v , u ) ?
Respuesta:
Proceso:
NO
No se hace nada.
u
v
5


-2
6
z
Lista de Arcos
-4
0
8
7
-3
7
x
2

y
9
Paso 1.5
V
[
]
=
{
u v
x
y
z
}
d
[
]
=
{
    0
}
P
[
]
=
{
}

(u,v)
(u,x)
(u,y)
(v,u)
(x,v) 
(x,y)
(y,v)
(y,z)
(z,u)
(z,x)
Aplicar Relax al Arco (x,v)
Pregunta: ¿ d[v] > d[x] + w( x , v ) ?
Respuesta:
Proceso:
NO
No se hace nada.
u
v
5


-2
6
z
Lista de Arcos
-4
0
8
7
-3
7
x
2

y
9
Paso 1.6
V
[
]
=
{
u v
x
y
z
}
d
[
]
=
{
    0
}
P
[
]
=
{
}

(u,v)
(u,x)
(u,y)
(v,u)
(x,v)
(x,y) 
(y,v)
(y,z)
(z,u)
(z,x)
Aplicar Relax al Arco (x,y)
Pregunta: ¿ d[y] > d[x] + w( x , y ) ?
Respuesta:
Proceso:
NO
No se hace nada.
u
v
5


-2
6
z
Lista de Arcos
-4
0
8
7
-3
7
x
2

y
9
Paso 1.7
V
[
]
=
{
u v
x
y
z
}
d
[
]
=
{
    0
}
P
[
]
=
{
}

(u,v)
(u,x)
(u,y)
(v,u)
(x,v)
(x,y)
(y,v) 
(y,z)
(z,u)
(z,x)
Aplicar Relax al Arco (y,v)
Pregunta: ¿ d[v] > d[y] + w( y , v ) ?
Respuesta:
Proceso:
NO
No se hace nada.
u
v
5


-2
6
z
Lista de Arcos
-4
0
8
7
-3
7
x
2

y
9
Paso 1.8
V
[
]
=
{
u v
x
y
z
}
d
[
]
=
{
    0
}
P
[
]
=
{
}

(u,v)
(u,x)
(u,y)
(v,u)
(x,v)
(x,y)
(y,v)
(y,z) 
(z,u)
(z,x)
Aplicar Relax al Arco (y,v)
Pregunta: ¿ d[z] > d[y] + w( y , z ) ?
Respuesta:
Proceso:
NO
No se hace nada.
u
v
5

z
(u,v)
(u,x)
(u,y)
(v,u)
(x,v)
(x,y)
(y,v)
(y,z)
(z,u) 
(z,x)

-2
6
Lista de Arcos
-4
0
8
7
-3
7
x
2

9
y
Paso 1.9
V
[
]
=
{
u v
x
y
z
}
d
[
]
=
{
    0
}
P
[
]
=
{
}

Aplicar Relax al Arco (z,u)
Pregunta: ¿ d[u] > d[z] + w( z , u ) ?
Respuesta:
SI
Proceso: d[u] = d[z] + w( z, u ) y P[u] = z
u
v
5
-2
z
(u,v)
(u,x)
(u,y)
(v,u)
(x,v)
(x,y)
(y,v)
(y,z)
(z,u) 
(z,x)

6
6
Lista de Arcos
-4
0
8
7
-3
7
x
2

9
y
Paso 1.9
V
[
]
=
{
u v
x
y
z
}
d
[
]
=
{
6    0
}
P
[
]
=
{
z
}

Aplicar Relax al Arco (z,u)
Pregunta: ¿ d[u] > d[z] + w( z , u ) ?
Respuesta:
SI
Proceso: d[u] = d[z] + w( z, u ) y P[u] = z
u
v
5
-2
z
(u,v)
(u,x)
(u,y)
(v,u)
(x,v)
(x,y)
(y,v)
(y,z)
(z,u)
(z,x) 

6
6
Lista de Arcos
-4
0
8
7
-3
7
x
2

9
y
Paso 1.10
V
[
]
=
{
u v
x
y
z
}
d
[
]
=
{
6    0
}
P
[
]
=
{
z
}

Aplicar Relax al Arco (z,x)
Pregunta: ¿ d[x] > d[z] + w( z , x ) ?
Respuesta:
SI
Proceso: d[x] = d[z] + w( z, x ) y P[x] = z
u
v
5
-2
z
(u,v)
(u,x)
(u,y)
(v,u)
(x,v)
(x,y)
(y,v)
(y,z)
(z,u)
(z,x) 

6
6
Lista de Arcos
-4
0
8
7
-3
7
x
2
7
9
y
Paso 1.10
V
[
]
=
{
u v
x
z
}
d
[
]
=
{
6  7  0
}
P
[
]
=
{
z
}
z
y

Aplicar Relax al Arco (z,x)
Pregunta: ¿ d[x] > d[z] + w( z , x ) ?
Respuesta:
SI
Proceso: d[x] = d[z] + w( z, x ) y P[x] = z
u
v
5
-2
z
(u,v) 
(u,x)
(u,y)
(v,u)
(x,v)
(x,y)
(y,v)
(y,z)
(z,u)
(z,x)

6
6
Lista de Arcos
-4
0
8
7
-3
7
x
2
7
9
y
Paso 2.1
V
[
]
=
{
u v
x
z
}
d
[
]
=
{
6  7  0
}
P
[
]
=
{
z
}
z
y

Aplicar Relax al Arco (u,v)
Pregunta: ¿ d[v] > d[u] + w( u , v ) ?
Respuesta:
SI
Proceso: d[v] = d[u] + w( u, v ) y P[v] = u
u
v
5
6
Lista de Arcos
(u,v) 
(u,x)
(u,y)
(v,u)
(x,v)
(x,y)
(y,v)
(y,z)
(z,u)
(z,x)
11
-2
6
z
-4
0
8
7
-3
7
x
2
7
9
y
Paso 2.1
V
[
]
=
{ u v
z
}
d
[
]
=
{ 6 11 7  0
}
P
[
]
=
{ z
}
u
x
z
y

Aplicar Relax al Arco (u,v)
Pregunta: ¿ d[v] > d[u] + w( u , v ) ?
Respuesta:
SI
Proceso: d[v] = d[u] + w( u, v ) y P[v] = u
u
v
5
6
Lista de Arcos
11
-2
6
z
-4
0
8
7
-3
7
x
2
7
y
9
Paso 2.2
V
[
]
=
{ u v
z
}
d
[
]
=
{ 6 11 7  0
}
P
[
]
=
{ z
}
u
x
z
y

(u,v)
(u,x) 
(u,y)
(v,u)
(x,v)
(x,y)
(y,v)
(y,z)
(z,u)
(z,x)
Aplicar Relax al Arco (u,x)
Pregunta: ¿ d[x] > d[u] + w( u , x ) ?
Respuesta:
Proceso:
NO
No se hace nada.
u
v
5
6
Lista de Arcos
(u,v)
(u,x)
(u,y) 
(v,u)
(x,v)
(x,y)
(y,v)
(y,z)
(z,u)
(z,x)
11
-2
6
z
-4
0
8
7
-3
7
x
2
7
9
y
Paso 2.3
V
[
]
=
{ u
v
z
}
d
[
]
=
{ 6 11 7  0
}
P
[
]
=
{ z
}
u
x y
z

Aplicar Relax al Arco (u,y)
Pregunta: ¿ d[y] > d[u] + w( u , y ) ?
Respuesta:
SI
Proceso: d[y] = d[u] + w( u, y ) y P[y] = u
u
v
5
6
Lista de Arcos
(u,v)
(u,x)
(u,y) 
(v,u)
(x,v)
(x,y)
(y,v)
(y,z)
(z,u)
(z,x)
11
-2
6
z
-4
0
8
7
-3
7
x
2
7
9
y
Paso 2.3
V
[
]
=
{ u
v
x y
z
}
d
[
]
=
{ 6 11 7 2
0
}
P
[
]
=
{ z
u
z u
}
2
Aplicar Relax al Arco (u,y)
Pregunta: ¿ d[y] > d[u] + w( u , y ) ?
Respuesta:
SI
Proceso: d[y] = d[u] + w( u, y ) y P[y] = u
u
v
5
6
Lista de Arcos
11
-2
6
z
-4
0
8
7
-3
7
x
2
7
y
9
Paso 2.4
V
[
]
=
{ u
v
x y
z
}
d
[
]
=
{ 6 11 7 2
0
}
P
[
]
=
{ z
u
z u
}
2
(u,v)
(u,x)
(u,y)
(v,u) 
(x,v)
(x,y)
(y,v)
(y,z)
(z,u)
(z,x)
Aplicar Relax al Arco (v,u)
Pregunta: ¿ d[u] > d[v] + w( v , u ) ?
Respuesta:
Proceso:
NO
No se hace nada.
u
v
5
6
Lista de Arcos
(u,v)
(u,x)
(u,y)
(v,u)
(x,v) 
(x,y)
(y,v)
(y,z)
(z,u)
(z,x)
11
-2
6
z
-4
0
8
7
-3
7
x
2
7
9
y
Paso 2.5
V
[
]
=
{ u
v
x y
z
}
d
[
]
=
{ 6 11 7 2
0
}
P
[
]
=
{ z
u
z u
}
2
Aplicar Relax al Arco (x,v)
Pregunta: ¿ d[v] > d[x] + w( x , v ) ?
Respuesta:
SI
Proceso:d[y] = d[x] + w( x, v ) y P[y] = x
u
v
5
6
Lista de Arcos
(u,v)
(u,x)
(u,y)
(v,u)
(x,v) 
(x,y)
(y,v)
(y,z)
(z,u)
(z,x)
4
-2
6
z
-4
0
8
7
-3
7
x
2
7
9
y
Paso 2.5
V
[
]
=
{
u v
x
y
z
}
d
[
]
=
{
6
4
7
2
0
}
P
[
]
=
{
z
x
z
u
}
2
Aplicar Relax al Arco (x,v)
Pregunta: ¿ d[v] > d[x] + w( x , v ) ?
Respuesta:
SI
Proceso: d[y] = d[x] + w( x, v ) y P[y] = x
u
v
5
6
Lista de Arcos
4
-2
6
z
-4
0
8
7
-3
7
x
2
7
y
9
Paso 2.6
V
[
]
=
{
u v
x
y
z
}
d
[
]
=
{
6
4
7
2
0
}
P
[
]
=
{
z
x
z
u
}
2
(u,v)
(u,x)
(u,y)
(v,u)
(x,v)
(x,y) 
(y,v)
(y,z)
(z,u)
(z,x)
Aplicar Relax al Arco (x,y)
Pregunta: ¿ d[y] > d[x] + w( x , y ) ?
Respuesta:
Proceso:
NO
No se hace nada.
u
v
5
6
Lista de Arcos
4
-2
6
z
-4
0
8
7
-3
7
x
2
7
y
9
Paso 2.7
V
[
]
=
{
u v
x
y
z
}
d
[
]
=
{
6
4
7
2
0
}
P
[
]
=
{
z
x
z
u
}
2
(u,v)
(u,x)
(u,y)
(v,u)
(x,v)
(x,y)
(y,v) 
(y,z)
(z,u)
(z,x)
Aplicar Relax al Arco (y,v)
Pregunta: ¿ d[v] > d[y] + w( y , v ) ?
Respuesta:
Proceso:
NO
No se hace nada.
u
v
5
6
Lista de Arcos
4
-2
6
z
-4
0
8
7
-3
7
x
2
7
y
9
Paso 2.8
V
[
]
=
{
u v
x
y
z
}
d
[
]
=
{
6
4
7
2
0
}
P
[
]
=
{
z
x
z
u
}
2
(u,v)
(u,x)
(u,y)
(v,u)
(x,v)
(x,y)
(y,v)
(y,z) 
(z,u)
(z,x)
Aplicar Relax al Arco (y,z)
Pregunta: ¿ d[z] > d[y] + w( y , z ) ?
Respuesta:
Proceso:
NO
No se hace nada.
u
v
5
6
Lista de Arcos
4
-2
6
z
-4
0
8
7
-3
7
x
2
7
y
9
Paso 2.9
V
[
]
=
{
u v
x
y
z
}
d
[
]
=
{
6
4
7
2
0
}
P
[
]
=
{
z
x
z
u
}
2
(u,v)
(u,x)
(u,y)
(v,u)
(x,v)
(x,y)
(y,v)
(y,z)
(z,u) 
(z,x)
Aplicar Relax al Arco (z,u)
Pregunta: ¿ d[u] > d[z] + w( z , u ) ?
Respuesta:
Proceso:
NO
No se hace nada.
u
v
5
6
Lista de Arcos
4
-2
6
z
-4
0
8
7
-3
7
x
2
7
y
9
Paso 2.10
V
[
]
=
{
u v
x
y
z
}
d
[
]
=
{
6
4
7
2
0
}
P
[
]
=
{
z
x
z
u
}
2
(u,v)
(u,x)
(u,y)
(v,u)
(x,v)
(x,y)
(y,v)
(y,z)
(z,u)
(z,x) 
Aplicar Relax al Arco (z,x)
Pregunta: ¿ d[x] > d[z] + w( z , x ) ?
Respuesta:
Proceso:
NO
No se hace nada.
u
v
5
6
Lista de Arcos
4
-2
6
z
-4
0
8
7
-3
7
x
2
7
y
9
Paso 3.1
V
[
]
=
{
u v
x
y
z
}
d
[
]
=
{
6
4
7
2
0
}
P
[
]
=
{
z
x
z
u
}
2
(u,v) 
(u,x)
(u,y)
(v,u)
(x,v)
(x,y)
(y,v)
(y,z)
(z,u)
(z,x)
Aplicar Relax al Arco (u,v)
Pregunta: ¿ d[v] > d[u] + w( u , v ) ?
Respuesta:
Proceso:
NO
No se hace nada.
u
v
5
6
Lista de Arcos
4
-2
6
z
-4
0
8
7
-3
7
x
2
7
y
9
Paso 3.2
V
[
]
=
{
u v
x
y
z
}
d
[
]
=
{
6
4
7
2
0
}
P
[
]
=
{
z
x
z
u
}
2
(u,v)
(u,x) 
(u,y)
(v,u)
(x,v)
(x,y)
(y,v)
(y,z)
(z,u)
(z,x)
Aplicar Relax al Arco (u,x)
Pregunta: ¿ d[x] > d[u] + w( u , x ) ?
Respuesta:
Proceso:
NO
No se hace nada.
u
v
5
6
Lista de Arcos
4
-2
6
z
-4
0
8
7
-3
7
x
2
7
y
9
Paso 3.3
V
[
]
=
{
u v
x
y
z
}
d
[
]
=
{
6
4
7
2
0
}
P
[
]
=
{
z
x
z
u
}
2
(u,v)
(u,x)
(u,y) 
(v,u)
(x,v)
(x,y)
(y,v)
(y,z)
(z,u)
(z,x)
Aplicar Relax al Arco (u,y)
Pregunta: ¿ d[y] > d[u] + w( u , y ) ?
Respuesta:
Proceso:
NO
No se hace nada.
u
v
5
6
Lista de Arcos
(u,v)
(u,x)
(u,y)
(v,u) 
(x,v)
(x,y)
(y,v)
(y,z)
(z,u)
(z,x)
4
-2
6
z
-4
0
8
7
-3
7
x
2
7
9
y
Paso 3.4
V
[
]
=
{
u v
x
y
z
}
d
[
]
=
{
6
4
7
2
0
}
P
[
]
=
{
z
x
z
u
}
2
Aplicar Relax al Arco (v, u)
Pregunta: ¿ d[u] > d[v] + w( v , u ) ?
Respuesta:
SI
Proceso: d[u] = d[v] + w( v, u ) y P[u] = v
u
v
5
2
Lista de Arcos
(u,v)
(u,x)
(u,y)
(v,u) 
(x,v)
(x,y)
(y,v)
(y,z)
(z,u)
(z,x)
4
-2
6
z
-4
0
8
7
-3
7
x
2
7
9
y
Paso 3.4
V
[
]
=
{
u v
x
y
z
}
d
[
]
=
{
2
4
7
2
0
}
P
[
]
=
{
v
x
z
u
}
2
Aplicar Relax al Arco (v, u)
Pregunta: ¿ d[u] > d[v] + w( v , u ) ?
Respuesta:
SI
Proceso: d[u] = d[v] + w( v, u ) y P[u] = v
u
v
5
2
Lista de Arcos
4
-2
6
z
-4
0
8
7
-3
7
x
2
7
y
9
Paso 3.5
V
[
]
=
{
u v
x
y
z
}
d
[
]
=
{
2
4
7
2
0
}
P
[
]
=
{
v
x
z
u
}
2
(u,v)
(u,x)
(u,y)
(v,u)
(x,v) 
(x,y)
(y,v)
(y,z)
(z,u)
(z,x)
Aplicar Relax al Arco (x, v)
Pregunta: ¿ d[v] > d[x] + w( x , v ) ?
Respuesta:
Proceso:
NO
No se hace nada.
u
v
5
2
Lista de Arcos
4
-2
6
z
-4
0
8
7
-3
7
x
2
7
y
9
Paso 3.6
V
[
]
=
{
u v
x
y
z
}
d
[
]
=
{
2
4
7
2
0
}
P
[
]
=
{
v
x
z
u
}
2
(u,v)
(u,x)
(u,y)
(v,u)
(x,v)
(x,y) 
(y,v)
(y,z)
(z,u)
(z,x)
Aplicar Relax al Arco (x, y)
Pregunta: ¿ d[y] > d[x] + w( x , y ) ?
Respuesta:
Proceso:
NO
No se hace nada.
u
v
5
2
Lista de Arcos
4
-2
6
z
-4
0
8
7
-3
7
x
2
7
y
9
Paso 3.7
V
[
]
=
{
u v
x
y
z
}
d
[
]
=
{
2
4
7
2
0
}
P
[
]
=
{
v
x
z
u
}
2
(u,v)
(u,x)
(u,y)
(v,u)
(x,v)
(x,y)
(y,v) 
(y,z)
(z,u)
(z,x)
Aplicar Relax al Arco (y, v)
Pregunta: ¿ d[v] > d[y] + w( y , v ) ?
Respuesta:
Proceso:
NO
No se hace nada.
u
v
5
2
Lista de Arcos
4
-2
6
z
-4
0
8
7
-3
7
x
2
7
y
9
Paso 3.8
V
[
]
=
{
u v
x
y
z
}
d
[
]
=
{
2
4
7
2
0
}
P
[
]
=
{
v
x
z
u
}
2
(u,v)
(u,x)
(u,y)
(v,u)
(x,v)
(x,y)
(y,v)
(y,z) 
(z,u)
(z,x)
Aplicar Relax al Arco (y, z)
Pregunta: ¿ d[z] > d[y] + w( y , z ) ?
Respuesta:
Proceso:
NO
No se hace nada.
u
v
5
2
Lista de Arcos
4
-2
6
z
-4
0
8
7
-3
7
x
2
7
y
9
Paso 3.9
V
[
]
=
{
u v
x
y
z
}
d
[
]
=
{
2
4
7
2
0
}
P
[
]
=
{
v
x
z
u
}
2
(u,v)
(u,x)
(u,y)
(v,u)
(x,v)
(x,y)
(y,v)
(y,z)
(z,u) 
(z,x)
Aplicar Relax al Arco (z, u)
Pregunta: ¿ d[u] > d[z] + w( z , u ) ?
Respuesta:
Proceso:
NO
No se hace nada.
u
v
5
2
Lista de Arcos
4
-2
6
z
-4
0
8
7
-3
7
x
2
7
y
9
Paso 3.10
V
[
]
=
{
u v
x
y
z
}
d
[
]
=
{
2
4
7
2
0
}
P
[
]
=
{
v
x
z
u
}
2
(u,v)
(u,x)
(u,y)
(v,u)
(x,v)
(x,y)
(y,v)
(y,z)
(z,u)
(z,x) 
Aplicar Relax al Arco (z, x)
Pregunta: ¿ d[x] > d[z] + w( z , x ) ?
Respuesta:
Proceso:
NO
No se hace nada.
u
v
5
2
Lista de Arcos
4
-2
6
z
-4
0
8
7
-3
7
x
2
7
y
9
Paso 4.1
V
[
]
=
{
u v
x
y
z
}
d
[
]
=
{
2
4
7
2
0
}
P
[
]
=
{
v
x
z
u
}
2
(u,v) 
(u,x)
(u,y)
(v,u)
(x,v)
(x,y)
(y,v)
(y,z)
(z,u)
(z,x)
Aplicar Relax al Arco (u, v)
Pregunta: ¿ d[v] > d[u] + w( u , v ) ?
Respuesta:
Proceso:
NO
No se hace nada.
u
v
5
2
Lista de Arcos
4
-2
6
z
-4
0
8
7
-3
7
x
2
7
y
9
Paso 4.2
V
[
]
=
{
u v
x
y
z
}
d
[
]
=
{
2
4
7
2
0
}
P
[
]
=
{
v
x
z
u
}
2
(u,v)
(u,x) 
(u,y)
(v,u)
(x,v)
(x,y)
(y,v)
(y,z)
(z,u)
(z,x)
Aplicar Relax al Arco (u, x)
Pregunta: ¿ d[x] > d[u] + w( u , x ) ?
Respuesta:
Proceso:
NO
No se hace nada.
u
v
5
2
Lista de Arcos
(u,v)
(u,x)
(u,y) 
(v,u)
(x,v)
(x,y)
(y,v)
(y,z)
(z,u)
(z,x)
4
-2
6
z
-4
0
8
7
-3
7
x
2
7
9
y
Paso 4.3
V
[
]
=
{
u v
x
y
z
}
d
[
]
=
{
2
4
7
2
0
}
P
[
]
=
{
v
x
z
u
}
2
Aplicar Relax al Arco (u, y)
Pregunta: ¿ d[y] > d[u] + w( u , y ) ?
Respuesta:
SI
Proceso: d[y] = d[u] + w( u, y ) y P[y] = u
u
v
5
2
Lista de Arcos
(u,v)
(u,x)
(u,y) 
(v,u)
(x,v)
(x,y)
(y,v)
(y,z)
(z,u)
(z,x)
4
-2
6
z
-4
0
8
7
-3
7
x
2
7
9
y
Paso 4.3
V
[
]
=
{
u v
x
y
d
[
]
=
{
2
4
7 -2 0 }
P
[
]
=
{
v
x
z
u
z }
}
-2
Aplicar Relax al Arco (u, y)
Pregunta: ¿ d[y] > d[u] + w( u , y ) ?
Respuesta:
SI
Proceso: d[y] = d[u] + w( u, y ) y P[y] = u
u
v
5
2
Lista de Arcos
4
-2
6
z
-4
0
8
7
-3
7
x
2
7
y
9
Paso 4.4
V
[
]
=
{
u v
x
y
d
[
]
=
{
2
4
7 -2 0 }
P
[
]
=
{
v
x
z
u
z }
}
-2
(u,v)
(u,x)
(u,y)
(v,u) 
(x,v)
(x,y)
(y,v)
(y,z)
(z,u)
(z,x)
Aplicar Relax al Arco (v, u)
Pregunta: ¿ d[u] > d[v] + w( v , u ) ?
Respuesta:
Proceso:
NO
No se hace nada.
u
v
5
2
Lista de Arcos
4
-2
6
z
-4
0
8
7
-3
7
x
2
7
y
9
Paso 4.5
V
[
]
=
{
u v
x
y
d
[
]
=
{
2
4
7 -2 0 }
P
[
]
=
{
v
x
z
u
z }
}
-2
(u,v)
(u,x)
(u,y)
(v,u)
(x,v) 
(x,y)
(y,v)
(y,z)
(z,u)
(z,x)
Aplicar Relax al Arco (x, v)
Pregunta: ¿ d[v] > d[x] + w( x , v ) ?
Respuesta:
Proceso:
NO
No se hace nada.
u
v
5
2
Lista de Arcos
4
-2
6
z
-4
0
8
7
-3
7
x
2
7
y
9
Paso 4.6
V
[
]
=
{
u v
x
y
d
[
]
=
{
2
4
7 -2 0 }
P
[
]
=
{
v
x
z
u
z }
}
-2
(u,v)
(u,x)
(u,y)
(v,u)
(x,v)
(x,y) 
(y,v)
(y,z)
(z,u)
(z,x)
Aplicar Relax al Arco (x, y)
Pregunta: ¿ d[y] > d[x] + w( x , y ) ?
Respuesta:
Proceso:
NO
No se hace nada.
u
v
5
2
Lista de Arcos
4
-2
6
z
-4
0
8
7
-3
7
x
2
7
y
9
Paso 4.7
V
[
]
=
{
u v
x
y
d
[
]
=
{
2
4
7 -2 0 }
P
[
]
=
{
v
x
z
u
z }
}
-2
(u,v)
(u,x)
(u,y)
(v,u)
(x,v)
(x,y)
(y,v) 
(y,z)
(z,u)
(z,x)
Aplicar Relax al Arco (y, v)
Pregunta: ¿ d[v] > d[y] + w( y , v ) ?
Respuesta:
Proceso:
NO
No se hace nada.
u
v
5
2
Lista de Arcos
4
-2
6
z
-4
0
8
7
-3
7
x
2
7
y
9
Paso 4.8
V
[
]
=
{
u v
x
y
d
[
]
=
{
2
4
7 -2 0 }
P
[
]
=
{
v
x
z
u
z }
}
-2
(u,v)
(u,x)
(u,y)
(v,u)
(x,v)
(x,y)
(y,v)
(y,z) 
(z,u)
(z,x)
Aplicar Relax al Arco (y, z)
Pregunta: ¿ d[z] > d[y] + w( y , z ) ?
Respuesta:
Proceso:
NO
No se hace nada.
u
v
5
2
Lista de Arcos
4
-2
6
z
-4
0
8
7
-3
7
x
2
7
y
9
Paso 4.9
V
[
]
=
{
u v
x
y
d
[
]
=
{
2
4
7 -2 0 }
P
[
]
=
{
v
x
z
u
z }
}
-2
(u,v)
(u,x)
(u,y)
(v,u)
(x,v)
(x,y)
(y,v)
(y,z)
(z,u) 
(z,x)
Aplicar Relax al Arco (z, u)
Pregunta: ¿ d[u] > d[z] + w( z , u ) ?
Respuesta:
Proceso:
NO
No se hace nada.
u
v
5
2
Lista de Arcos
4
-2
6
z
-4
0
8
7
-3
7
x
2
7
y
9
Paso 4.10
V
[
]
=
{
u v
x
y
d
[
]
=
{
2
4
7 -2 0 }
P
[
]
=
{
v
x
z
u
z }
}
-2
(u,v)
(u,x)
(u,y)
(v,u)
(x,v)
(x,y)
(y,v)
(y,z)
(z,u)
(z,x) 
Aplicar Relax al Arco (z, x)
Pregunta: ¿ d[x] > d[z] + w( z , x ) ?
Respuesta:
Proceso:
NO
No se hace nada.
u
5
2
v
Lista de Arcos
4
(u,v)
(u,x)
(u,y)
(v,u)
(x,v)
(x,y)
(y,v)
(y,z)
(z,u)
(z,x)
-2
6
z
-4
0
8
7
-3
7
x
2
7
9
y
-2
Paso 5.0
V
[
]
=
{
u v
x
y
d
[
]
=
{
2
4
7 -2 0 }
P
[
]
=
{
v
x
z
u
z }
}
Verificar en cada arco que se
cumple la condición:
d[Vf] <= d[Vi] + w( Vi , Vf )
Si no se cumple:
=> NO EXISTE SOLUCIÓN.
u
v
Lista de Arcos
2
4
(u,v)
(u,x)
(u,y)
(v,u)
(x,v)
(x,y)
(y,v)
(y,z)
(z,u)
(z,x)
-2
z
-4
0
-3
7
x
7
y
-2
SOLUCIÓN
V
[
]
=
{
u v
x
y
d
[
]
=
{
2
4
7 -2 0 }
P
[
]
=
{
v
x
z
u
z }
}
Descargar

BellMan Ford Animación - upcAnalisisAlgoritmos