PDF de programación - Algoritmo de Dijkstra para resolver el problema del camino más corto

15.053 Martes, 2 de abril

El problema del flujo de coste mínimo

El problema del camino más corto
Algoritmo de Dijkstra para resolver el

problema del camino más corto

Entregas: material de clase

Grafo dirigido G = (N, A).

Conj. nodos N, conj. arcos A;
Capacidades uij en arco (i,j)
lím. inferior 0 en arco (i,j)
Coste cij en arco (i,j)
Oferta/demanda bi para nodo i.
(El valor positivo indica oferta)

Una red con costes, capacidades,
ofertas, demandas

3
2

-3, 6$

3, 4$

2, 7$

4

-2

4

1

8, 5$

7, 2$

3

-5

Minimice el coste del envío de flujo
s.a Flujo salida i - Flujo entrada i = bi

0 ≤ xij ≤ uij

2

El problema del camino más corto

1

2

4

2

1

3

4

2

3

4

3

5

2

2

6

¿Cuál es el camino más corto de un nodo origen (a menudo
indicado como s) a un nodo receptor, (indicado como t)?
¿Cuál es el camino más corto desde el nodo 1 al nodo 6?
Para esta clase damos por hecho que:
1. Existe un camino desde el origen al resto de los nodos.
2. Todas las longitudes de arco son positivas.

4

1

3

Formulación

En general la formulación de PL se da así:

Minimice

sujeto a

c x
ij

ij

n

n

∑∑

=
1

j

i

=
1
n

n

ij

−

x

∑ ∑
=
=
j
k
1
1
≤
≤
u
0
ij

x

ij

x

= ∀ =

b
i

,

i

ki

,
1

…

,

n

Formulación como programación lineal

Otra formulación

En general la formulación PL para el camino más corto de
un nodo de origen, s, a un receptor, t, viene dada como

La formulación PL para el camino más corto desde
un nodo origen, s, al resto de los nodos viene dada como

Minimizar

siempre que

n

n

∑∑

=
1

i

=
1

j

c x
ij

ij

n

∑ ∑

x

−

ij

n

=
1

j

k

=
1

x

≥

0

,

∀
ij

x

ki

,
1


= −
,
1


,
0


i
i

=
=

s
t

∀ =
i
de otro modo

Minimizar

siempre que

,
1

…

,

n

5

n

n

∑∑

=
1

i

=
1

j

c x
ij

ij

n

n

ij

−

x

∑ ∑
=
=
j
k
1
1
≥
∀
x
ij

,
0

x

ki

−
n
,
1

=  −
,
1


=

i
s
,
∈ −
i N s
{ }

6

Algunas preguntas sobre el problema
del camino más corto
¿Dónde se da en la práctica?

– Aplicaciones directas
– Aplicaciones indirectas (y a menudo ingeniosas)

¿Cómo se resuelve el problema del camino más corto?

– Algoritmo de Dijkstra

¿Cómo se mide el rendimiento de un algoritmo?

¿Cómo se establece que una solución es en verdad

– Control del tiempo de la CPU
– Garantías de rendimiento

el camino más corto?
– Conexión con dualidad PL

Puntuaciones deportivas

El flumbaya es un deporte acuático poco

común en el que hay dos tipos de puntuación
posible. O bien marcar un gymbol, que
vale 7 puntos, o bien marcar un
quasher, que vale 5 puntos. Un comentarista
de TV afirma que en un partido reciente
un equipo ganó por 19 a 18. ¿Es esto
posible?

7

8

Más sobre flumbaya

0

1

8

2

9

3

4

5

6

7

10

11

12

13

14

No hay
camino del
nodo 0 al
nodo 18. Un
tanteo de 18
es imposible.

15

16

17

18

19

9

Más sobre flumbaya
Datos: Gymbol vale n1 puntos
Quasher vale n2 puntos:
determinar si se pueden marcar q puntos

La red: G = (N, A), donde N = {0, …, q}

para cada nodo j = 0 a q – n 1 , (j, j+n1) ∈ A
para cada nodo j = 0 a q – n 2, (j, j+n2) ∈ A

Pregunta: ¿hay un camino en G del nodo 0 al nodo q?
Hecho: si n1 y n2 no tienen un divisor común entero (salvo
1 y –1), entonces el número de marcadores que no se pueden
dar es (n1-1)(n2-1)/2. Se dará una puntuación extra por
demostrar este hecho. (Ojo: es difícil de probar.)

10

Una aplicación indirecta: hallar un formato
de párrafo óptimo

Una aplicación indirecta: hallar un formato
de párrafo óptimo

for each

TeX optimally decomposes paragraphs by
selecting the breakpoints
line
optimally. It has a subroutine that computes
the attractiveness F(i,j) of a line that begins
at word i and ends at word j-1. How can one
use F(i,j) to create a shortest path problem
whose solution will solve the paragraph
problem?

It has

the breakpoints

TeX optimally decomposes paragraphs
for each
by selecting
line optimally.
subroutine
that computes the attractiveness F(i,j) of a
line that begins at word i and ends at word
j-1. How can one use F(i,j) to create a
shortest path problem whose solution will
solve the paragraph problem?

a

a

It has

the breakpoints

TeX optimally decomposes paragraphs
by selecting
for each
line optimally.
subroutine
that computes the attractiveness F(i,j) of a
line that begins at word i and ends at word
j-1. How can one use F(i,j) to create a
shortest path problem whose solution will
solve the paragraph problem?
that

line

.2

.1

Tex

.2

selecting
by

.15
.15

.3

.3

line

1000
shortest

.2
0

solve

.1

.2
j-1

end

Cada palabra
corresponde a un nodo
y un arco (i,j)
indica que una línea
comienza por i
y termina por j-1.
Un camino de Tex a
“end” corresponde a
un formato de párrafo.

Un valor del camino es
la “fealdad” del
mismo.

Sobre el ejemplo del párrafo

n decisiones si-no diferentes

– Decisión j: Sí significa empezar una línea en la palabra j
–

No: no empezar una línea en la palabra j

El coste de cada decisión sí depende sólo de la

siguiente decisión sí
– f(i,j) era el coste de empezar una línea en la palabra i

asumiendo que la palabra j comienza la línea siguiente.

Cree un problema del camino más corto con nodos

1, 2, … , n+1 donde el coste del arco (i,j) es f(i,j). ¿Cuál
es el camino más corto de 1 a n+1

13

Aproximación de funciones lineales por tramos

Objetivo: aproximar f con menos puntos

– c* es el “coste” por punto incluido
– c36 = |a4 -b 4| + |a5 -b 5| = suma de errores. (Otras

métricas también serían correctas)

a6

a7

a5

a4

b5

b4

a3

f(x)

a2

a1

a10

f (x)1

f (x)2

a9

a8

x

(a)

Una aplicación en la compresión de datos:
aproximación de funciones lineales por tramos
Datos: una función lineal por tramos

– n puntos a1 = (x1,y1), a2 = (x2,y2),..., an = (xn,yn).
– x1 ≤ x2 ≤ ... ≤ xn.

Objetivo: aproximar f con menos puntos

– c* es el “coste” por punto incluido
– cij = coste de aproximar la función a través de los

puntos i, i+1, . . ., j-1 mediante una sola línea que una i
con j. (Suma de errores, o errores elevados al cuadrado)

a10

f (x)1

f (x)2

a6

a7

a9

a8

1

2

f(x)

a4

a3

a2

a1

x

3

(b)

4

5

14

Sobre la aproximación de funciones

n decisiones sí-no diferentes

– Decisión j: Sí significa seleccionar j
–

No: supone no seleccionar j

El coste de cada decisión sí depende sólo de la

siguiente decisión sí
– cij es el coste de seleccionar el punto i seguido por j, y

toma en cuenta el coste de seleccionar i, y los costes de
aproximar los puntos i+1, …, j-1.

Crear un problema del camino más corto con nodos
1, … ,n donde el coste del arco (i,j) es cij. ¿Cuál es el
camino más corto de 1 a n?

15

16

Algoritmo de Dijkstra para el problema
del camino más corto

1

2

4

2

1

3

4

2

3

4

3

5

2

2

6

Trabaje con
su compañero.
Halle el camino
más corto
inspeccionando

Ejercicio: halle el camino más corto desde 1 al resto
de los nodos. Registre las distancias con las etiquetas
d(i) y el predecesor inmediato de cada nodo, pred(i).

Un paso clave en los algoritmos del camino más corto

d( ) indica un vector de etiquetas de distancia temporal.
d(j) es la distancia de algún camino desde el nodo de

origen 1 al nodo j.

Actualización del proceso(i)

for each (i,j) ∈ A(i) do
si d(j) > d(i) + c ij entonces d(j) : = d(i) + cij y predec(j) : = i;

Camino P

1

10

62
i

78
j

d(1)= 0, pred(1)=0;
d(2) = 2, pred(2)=1

Halle las otras distancias, para incrementar
la distancia desde el nodo 1.

17

Hasta este punto, el mejor camino de 1 a j tiene la distancia 78

18

Un paso clave en los algoritmos del camino más corto

d( ) indica un vector de etiquetas de distancia temporal.
d(j) es la distancia de algún camino desde el nodo de

origen 1 al nodo j.

Actualización del proceso(i)

for each (i,j) ∈ A(i) do
if d(j) > d(i) + cij then d(j) : = d(i) + cij y predec(j) : = i;

Camino P

1

10

62
i

72
78
j

P(1,j) es un “camino” de 1 a j de distancia 72.

19

fin

fin

Algoritmo de Dijkstra

inicio

d(s) : = 0 y predec(s) : = 0;
d(j) : = ∞ por cada j ∈ N - {s};
LIST : = {s};
mientras LIST ≠φ do
inicio

d(i) : = min {d(j) : j ∈ LIST};
eliminar nodo i de LIST;
actualizar( i)
si d(j) disminuye, poner j en LIST

Distancias inicialización
LIST = conjunto de
nodos temporales

Selec. el nodo i en
LIST con etiqueta de
distancia min., y
actualice(i)

20

Un ejemplo

d(2) = ∞
\ 2
1
pred(2) =
2
2

2

4

d(1) = 0
pred(1) = 0

1
1

4

1

2

d(4) = ∞
\ 6
2
pred(4) =

4
4

3

2

2

Reg
Registre los arcos
R
Pronfj
dei, y update
of i, and update
de i, y actualice
o i, and update
of i, and update
d( ), pred( ), y
d( ), pred( ), and
d( ), predec( ), y
d( ), pred( ), and
d( ), pred( ), and
LIST
LIST
LIST
LIST
LIST

d(6) = ∞
\ 6
5

6
6
pred(6) =

3
\ 3

3
3
d(3) = ∞
\ 4
\ 2
1
pred(3) =

5
5
d(5) = ∞
\ 4
2
pred(5) =

El
final

LIST = {1,

\ 2, 3,
\

\

\
4, 5,

\ 6}\

Halarnode i on
Hallar el nodo i en
Find the node i on
Find the node i on
Find the node i on
Hn
Initialize the
LIST with
LIST with
LIST con
LIST with
LIST with
LIST with
distances and
minimum
minimum
distancia
minimum
minimum
minimum
LIST.
dce.
distance.
mínima.
distanc.
distance.
distance.

El resultado del algoritmo
de Dijkstra

0

1

2

4

2
2

4

1

2

3

3
3

6
4

3

5

4

2

2

Phre h s
Para hallar el
camino más corto
ca
deor
desde el nodo j,
vaya inversamente
va
desde el nodo
al origen.

6

6

Dijkstra ofrece un camino más corto desde el nodo 1 al
resto de los nodos. Da un árbol de camino más corto.

Comentarios sobre el tiempo de ejecución

La solución rectil