Ruta Óptima

Diseño y Análisis de Algoritmos

Melissa Robles
Ruta óptima
● Encontrar el camino más corto entre dos nodos en es necesario en muchas
aplicaciones:
○ Transporte
○ Movimiento robótico
○ Comunicación
○ Optimización en ambulancias
Definiciones - Caminos de costo mínimo
Dado un grafo dirigido G = (V,E) y una función de pesos w: E →|R definimos

Camino entre v y w : Sucesión finita de vértices p = (v1, v2, …, vk) tal que
1. (vi,vi+1) ∈ E para todo i < k
2. v1 = v y vk = w

Peso total del camino p:

Definiciones - Caminos de costo mínimo
Dado un grafo dirigido G = (V,E) y una función de pesos w: E →|R definimos

Camino entre v y w : Sucesión finita de vértices p = (v1, v2, …, vk) tal que
1. (vi,vi+1) ∈ E para todo i < k
2. v1 = v y vk = w

Peso total del camino p:

Peso del camino de costo mínimo:

Camino de costo mínimo: Camino entre v y w cuyo peso es δ(v,w).

Single source shortest-paths problem
Single source shortest-paths problem
Dado un grafo G = (V,E), una función de pesos w, y un nodo específico s, queremos
encontrar el camino más corto entre s y cualquier otro vértice en V.

Otros problemas que podemos solucionar:

1. All-pairs shortest-paths problem: Encontrar el camino más corto entre cualquier

par de nodos del grafo.
2. Single-pair shortest-path problem: Encontrar el camino más corto entre dos
vértices fijos v y w.
3. Single-destination shortest-paths problem: Encontrar el camino más corto entre
cualquier nodo v en V y un nodo fijo t.
Single source shortest-paths problem
Dado un grafo G = (V,E), una función de pesos w, y un nodo específico s, queremos
encontrar el camino más corto entre s y cualquier otro vértice en V.

Single-destination shortest-paths problem: Encontrar el camino más corto entre

cualquier nodo v en V y un nodo fijo t.
Solución: Invertir la dirección de cada arista en el grafo original y solucionar el
problema de Single Source Shortest-paths problem.
Naturaleza sub-óptima del problema
Dado un grafo G = (V,E), una función de pesos w, y un nodo específico s, queremos
encontrar el camino más corto entre s y cualquier otro vértice en V.
Lema de suboptimalidad:

● Sea p=⟨v 0,v 1,…,v k⟩ un camino de costos mínimos desde el vértice v0 hasta el vértice vk.
● Definimos el subcamino pij=⟨vi,vi+1,…,vj⟩ como el tramo de p que va desde el vértice vi hasta el
vértice vj con 0 ≤ i ≤ j ≤ k.

Entonces, pij es también un camino de costo mínimo desde v i

hasta v j.

Demostración por contradicción: suponemos que

existe un camino q con menor costo entre vi y vj.

Si cambiamos el camino p por aquel que pasa por el

camino q entre vi y vj, encontramos un camino de
costo menor entre v0 y vk.
Naturaleza sub-óptima del problema
Dado un grafo G = (V,E), una función de pesos w, y un nodo específico s, queremos
encontrar el camino más corto entre s y cualquier otro vértice en V.

Lema de suboptimalidad:

Dado un grafo dirigido y ponderado sea p=⟨v 0,v 1,…,v k⟩ un camino de costos mínimos desde el
vértice v0 hasta el vértice vk. Para cualquier i y j tales que 0 ≤ i ≤ j ≤ k, definimos el subcamino pij=
⟨vi,vi+1,…,vj⟩ como el tramo de p que va desde el vértice vi hasta el vértice vj. Entonces, pij es también
un camino de costo mínimo desde v i hasta v j.

¡Podemos usar las técnicas que ya conocemos! Por ejemplo, programación dinámica.
Naturaleza sub-óptima del problema
Dado un grafo G = (V,E), una función de pesos w, y un nodo específico s, queremos
encontrar el camino más corto entre s y cualquier otro vértice en V.

¿Cómo solucionamos el problema si w(v 1

,v 2) = 1 para todos los ejes?
Naturaleza sub-óptima del problema
Dado un grafo G = (V,E), una función de pesos w, y un nodo específico s, queremos
encontrar el camino más corto entre s y cualquier otro vértice en V.

¿Cómo solucionamos el problema si w(v 1

,v 2) = 1 para todos los ejes?
Pesos negativos
Dado un grafo G = (V,E), una función de pesos w, y un nodo específico s, queremos
encontrar el camino más corto entre s y cualquier otro vértice en V.

¿Qué problema hay con este grafo?

¿Cuál es el camino más corto entre s y g?

Pesos negativos
Dado un grafo G = (V,E), una función de pesos w, y un nodo específico s, queremos
encontrar el camino más corto entre s y cualquier otro vértice en V.

¿Qué problema hay con este grafo?

¿Cuál es el camino más corto entre s y g?

Hay un ciclo negativo (e -> f -> e). Para cualquier

camino que encuentre entre s y g puedo encontrar
un camino con un menor costo entrando a ese
ciclo.
δ(s, g) = -∞

El ciclo (c -> d -> c) no tiene el mismo problema

porque el costo total es positivo.
Árbol de caminos más cortos
Dado un grafo G = (V,E), una función de pesos w, y un nodo específico s, queremos
encontrar el camino más corto entre s y cualquier otro vértice en V.
Árbol de caminos más cortos
A partir de la solución del problema Single source shortest-paths problem, se puede construir un
subárbol del grafo T=(V’, E’) con raíz en s tal que:
1. V’ es el conjunto de todos los vértices que pueden ser alcanzados desde s
2. Para todo v ∈ V’, el camino entre s y v dado por el árbol es un camino de costo mínimo entre s y
v.
Los árboles representados
en b y c son dos árboles de
caminos más cortos.

Noten que los caminos más

cortos no son
necesariamente únicos.
Bellman Ford
Algoritmo Bellman Ford
El algoritmo de Bellman Ford soluciona el Single source
shortest-paths problem.

No tiene restricciones sobre el signo de los pesos del

grafo (a diferencia de Dijkstra)

● Estructuras utilizadas:
○ Arreglo r de tamaño |V| para guardar los
costos mínimos de llegar de s a cada vértice
del grafo.
○ (Opcional) Arreglo de tamaño |V| para
guardar los predecesores que forman el a´rbol
de caminos más cortos.

● Inicialización: Inicializar el costo de la fuente en

cero y los costos de los demás nodos en infinito.
Algoritmo Bellman Ford
● Se realizan |V|-1 iteraciones . En cada iteración se itera
sobre las aristas del grafo y se realiza el proceso de
relajación.

● Actualizo el costo mínimo de s a v comparando el

costo anterior de llegar a v con el costo de llegar de s a
w y luego de w a v.
s … v
…
w

● Si hay una actualización y estoy calculando el

predecesor lo actualizo.
Algoritmo Bellman Ford
● Se realizan |V|-1 iteraciones . En cada iteración se itera
sobre las aristas del grafo y se realiza el proceso de
relajación.

● Actualizo el costo mínimo de s a v comparando el

costo anterior de llegar a v con el costo de llegar de s a
w y luego de w a v.
s … v
…
w

● Si hay una actualización y estoy calculando el

predecesor lo actualizo.
Algoritmo Bellman Ford
● Se realizan |V|-1 iteraciones . En cada iteración se itera
sobre las aristas del grafo y se realiza el proceso de
relajación.

● Actualizo el costo mínimo de s a v comparando el

costo anterior de llegar a v con el costo de llegar de s a
w y luego de w a v.
s … v
…
w

● Si hay una actualización y estoy calculando el

predecesor lo actualizo.
Algoritmo Bellman Ford
● Relajación :
Actualizo el costo mínimo de s a v comparando el costo anterior de llegar a v con el costo de
llegar de s a w y luego de w a v.

s … v
…
w

● Propiedad de la relajación:

Si p=⟨v0,v1,…,vk⟩ es el camino más corto desde s=v0 hasta vk, y las aristas de p se relajan en orden
(v0,v1),(v1,v2),…,(vk-1,vk), entonces, al final de estas relajaciones:

r[vk]=δ(s,vk)
Algoritmo Bellman Ford
Propiedad de la relajación:

Si p=⟨v0,v1,…,vk⟩ es el camino más corto desde s=v0 hasta vk, y las aristas de p se relajan en orden
(v0,v1),(v1,v2),…,(vk-1,vk), entonces, al final de estas relajaciones:

r[vk]=δ(s,vk)

Caso base (k=0):

Antes de relajar cualquier arista del camino p, tenemos que, por la inicialización del algoritmo:

r[v0]=0=δ(s,s)
Algoritmo Bellman Ford
Propiedad de la relajación:

Si p=⟨v0,v1,…,vk⟩ es el camino más corto desde s=v0 hasta vk, y las aristas de p se relajan en orden
(v0,v1),(v1,v2),…,(vk-1,vk), entonces, al final de estas relajaciones:

r[vk]=δ(s,vk)

Paso inductivo (k>0):

Suponemos que r[vk-1] = δ(s,vk-1). En el momento en que relajamos (vk-1,vk), se actualiza r[vk]:

r[vk]=min{r[vk], r[vk-1]+w(vk-1,vk)}

= min{r[vk], δ(s,vk-1)+w(vk-1,vk)}

= min{r[vk], δ(s,vk)} = δ(s,vk)

por la naturaleza subóptima del problema y la definición de p
Algoritmo Bellman Ford
¿Por qué funciona?

● Si un grafo tiene |V| nodos, el camino más largo posible sin ciclos tiene a lo sumo |V|-1 aristas.

● Propiedad de la relajación:
Si p=⟨v0,v1,…,vk⟩ es el camino más corto desde s=v0 hasta vk, y las aristas de p se relajan en orden
(v0,v1),(v1,v2),…,(vk-1,vk), entonces, al final de estas relajaciones:

r[vk]=δ(s,vk)

● Intuición : Al relajar (v0,v1), garantizamos que r[v1] es óptimo. Luego, al relajar (v1,v2), propagamos
la distancia mínima a v2, y así sucesivamente hasta llegar a vk.
Algoritmo Bellman Ford
● Si al final de las iteraciones todavía es posible mejorar uno de los costos, significa que hay
un ciclo con peso negativo.
Algoritmo Bellman Ford
Implementación

Complejidad: O(VE)

* Depende de la representación del grafo.

Dijkstra
Dijkstra
● El algoritmo de Dijkstra soluciona el Single source shortest-paths problem para grafos
con pesos positivos.

● Idea : Almacenamos la distancia de s a todos los nodos cercanos, y estos se usan para
encontrar el camino más corto a nodos que sean más distantes.

● Podemos pensarlo como una generalización de BFS para grafos con pesos positivos: las
actualizaciones se van realizando por “olas” alejándose cada vez más del nodo inicial.

● Al igual que en BFS vamos a mantener un conjunto de vértices ya visitados, cuyo

camino de costos mínimos ya ha sido calculado.
Algoritmo Dijkstra

● Inicialización: Inicializar el costo de la fuente en

cero y los costos de los demás nodos en infinito.

● Informalmente, es un recorrido sencillo por los

vértices comenzando desde la fuente.

● Se realiza en 2 pasos:
1. Escoger el vértice v no escogido previamente al que
se llegue con costo mínimo desde los vértices ya
escogidos

2. Actualizar los costos mínimos a los vértices no

escogidos todavía usando v como posible vértice
intermedio
Algoritmo Dijkstra

● Inicialización: Inicializar el costo de la fuente en

cero y los costos de los demás nodos en infinito.

● Informalmente, es un recorrido sencillo por los

vértices comenzando desde la fuente.

● Se realiza en 2 pasos:
1. Escoger el vértice v no escogido previamente al que
se llegue con costo mínimo desde los vértices ya
escogidos

2. Actualizar los costos mínimos a los vértices no

escogidos todavía usando v como posible vértice
intermedio
Algoritmo Dijkstra

● Inicialización: Inicializar el costo de la fuente en

cero y los costos de los demás nodos en infinito.

● Informalmente, es un recorrido sencillo por los

vértices comenzando desde la fuente.

● Se realiza en 2 pasos:
1. Escoger el vértice v no escogido previamente al que
se llegue con costo mínimo desde los vértices ya
escogidos

2. Actualizar los costos mínimos a los vértices no

escogidos todavía usando v como posible vértice
intermedio
Algoritmo Dijkstra

● Inicialización: Inicializar el costo de la fuente en

cero y los costos de los demás nodos en infinito.

● Informalmente, es un recorrido sencillo por los

vértices comenzando desde la fuente.

● Se realiza en 2 pasos:
1. Escoger el vértice v no escogido previamente al que
se llegue con costo mínimo desde los vértices ya
escogidos

2. Actualizar los costos mínimos a los vértices no

escogidos todavía usando v como posible vértice
intermedio
Algoritmo Dijkstra

● Inicialización: Inicializar el costo de la fuente en

cero y los costos de los demás nodos en infinito.

● Informalmente, es un recorrido sencillo por los

vértices comenzando desde la fuente.

● Se realiza en 2 pasos:
1. Escoger el vértice v no escogido previamente al que
se llegue con costo mínimo desde los vértices ya
escogidos

2. Actualizar los costos mínimos a los vértices no

escogidos todavía usando v como posible vértice
intermedio
Algoritmo Dijkstra

● Inicialización: Inicializar el costo de la fuente en

cero y los costos de los demás nodos en infinito.

● Informalmente, es un recorrido sencillo por los

vértices comenzando desde la fuente.

● Se realiza en 2 pasos:
1. Escoger el vértice v no escogido previamente al que
se llegue con costo mínimo desde los vértices ya
escogidos

2. Actualizar los costos mínimos a los vértices no

escogidos todavía usando v como posible vértice
intermedio
Algoritmo Dijkstra
● Inicialización: Inicializar el costo de la fuente en
cero y los costos de los demás nodos en infinito.

● Informalmente, es un recorrido sencillo por los

vértices comenzando desde la fuente.

● Se realiza en 2 pasos:
1. Escoger el vértice v no escogido previamente al que
se llegue con costo mínimo desde los vértices ya
escogidos

2. Actualizar los costos mínimos a los vértices no

escogidos todavía usando v como posible vértice
intermedio
Algoritmo Dijkstra

● ¿Por qué no sirve el algoritmo para pesos negativos? Cuando proceso el nodo d
Algoritmo Dijkstra

Encuentro el nodo que no esté

marcado con costo mínimo.

Itero sobre los vecinos

de w que no están en A
(≤V)

Complejidad: O(V2)

* La implementación para encontrar el mínimo afecta la complejidad

Floyd-Warshall
Floyd-Warshall
● El algoritmo de Floyd-Warshall es un algoritmo de programación dinámica para
resolver el problema de All-pairs shortest-paths problem.

● Hasta ahora, ¿cómo podemos resolver este problema?

Correr el algoritmo de Dijkstra V veces (uno para cada

posible vértice de inicio) y seria O(V 3).

● Numeramos los vértices como V = {1, 2, .., n} y la función w la representamos en una

matriz Wij.

● Definimos dij como el costo mínimo entre los vértices i y j.

Floyd-Warshall
Definimos una función recursiva

m(i, j, k) = costo mínimo para ir del vértice i al vértice j , utilizando solamente algunos de
los primeros k vértices como intermedios

2 m(0,3,2) = ∞
0 2
1

4
(solo puedo usar como
3
vértices intermedios 0 y 1)
1

m(0,3,3) = 3
Floyd-Warshall
Definimos una función recursiva

m(i, j, k) = costo mínimo para ir del vértice i al vértice j , utilizando solamente algunos de
los primeros k vértices como intermedios

Caso base (k=0): No se pueden utilizar nodos intermedios.

El costo mínimo de ir de un nodo al otro sin nodos intermedios es el mismo costo de la

arista entre i y j.
m(i, j, 0) = Wij
Floyd-Warshall
m(i, j, k) = costo mínimo para ir del vértice i al vértice j , utilizando solamente algunos de
los primeros k vértices como intermedios

Caso base (k=0): m(i, j, 0) = Wij

Floyd-Warshall
m(i, j, k) = costo mínimo para ir del vértice i al vértice j , utilizando solamente algunos de
los primeros k vértices como intermedios
Caso recursivo (k>0):
Hay dos opciones para el último de los vértices que puedo usar como intermedios (el k-
ésimo vértice):
● El k-ésimo vértice está en el camino óptimo
● El k-ésimo vértice no está en el camino óptimo

m(3, 5, 2) = m(3, 5, 1)

En este caso, incluir el nodo 1 no mejora

el camino más corto entre 3 a 5 que es la
arista directa.
Floyd-Warshall
m(i, j, k) = costo mínimo para ir del vértice i al vértice j , utilizando solamente algunos de
los primeros k vértices como intermedios
Caso recursivo (k>0):
Hay dos opciones para el último de los vértices que puedo usar como intermedios (el k-
ésimo vértice):
● El k-ésimo vértice está en el camino óptimo
● El k-ésimo vértice no está en el camino óptimo

m(3, 5, 3) = m(3, 2, 2) + m(2, 5, 2) = 7

Floyd-Warshall

m(i,j,k-1)
j
j

i m(k-1,j,k-1)
k-1 i
k-1
m(i,k-1,k-1)
Floyd-Warshall

m(3,5,2) = ??

m(3,5,3) = ??
Floyd-Warshall

m(3,5,2) = ??

Opc 1: m(3,5,1) = 9
Opc 2: m(3,1,1)+m(1,5,1) = 16

m(3,5,3) = ??

Opc 1: m(3,5,2) = 9
Opc 2: m(3,2,2)+m(2,5,2)=3+4=7
Floyd-Warshall
Floyd-Warshall
m(i, j, k) = costo mínimo para ir del vértice i al vértice j , utilizando solamente algunos de
los primeros k vértices como intermedios

Ejercicio:
Complete la matriz para k = 1

m(1,3,1)
k=0