PDF de programación - Algoritmos con Python - El camino más corto

Algoritmos con Python

El camino más corto

4 de marzo de 2021

Índice

1 Propiedad de la composición

1.1 Vértices negros, grises y blancos . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Observación clave . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
1.3 Estructura de datos para los vértices grises

2 Gráficos con pesos 0 o 1

2.1 Definición . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 Aplicación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3 Algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3 Grafos con ponderaciones no negativas — Dijkstra

3.1 Definición . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2 Complejidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3 Algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.4 Colas de prioridad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.5 Una ligera mejora . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.6 Detalles de implementacion . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.7 Variante . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2
2
3
3

5
5
5
5

7
7
7
7
8
8
8
9

4 Gráficas con pesos arbitrarios — Bellman – Ford

11
4.1 Definición . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
4.2 Complejidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
4.3 Algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
4.4 Detección de ciclos negativos . . . . . . . . . . . . . . . . . . . . . . . . . . 12

5 Todas las rutas de origen-destino: Floyd-Warshall

13
5.1 Definición . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
5.2 Complejidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
5.3 Algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
5.4 Detalles de implementacion . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
5.5 Detección de ciclos negativos . . . . . . . . . . . . . . . . . . . . . . . . . . 14
5.6 Ejemplo: Rutas en Berland . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

6 Cuadrícula

15
6.1 Problema
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
6.2 El algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
6.3 Variantes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

7 Variantes

17
7.1 Grafos no ponderados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
7.2 Grafos acíclicos dirigidos
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
7.3 Camino más largo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
. . . . . . . . . . . . . . . . . . . . . . . . 18
7.4 El camino más largo de un árbol

I

7.5 Trayectoria que minimiza el peso máximo sobre los arcos . . . . . . . . . . . 18
7.6 Grafo ponderado en los vértices
. . . . . . . . . . . . . . . . . . . . . . . . 18
7.7 Ruta que minimiza el peso máximo en los vértices . . . . . . . . . . . . . . . 18
. . . . . . . . . . . 19
7.8 Todos los bordes que pertenecen a un camino más corto

II

Introducción

Un problema clásico de los grafos consiste en encontrar un camino más corto entre dos
vértices, una fuente s y un destino v. Por el mismo costo podemos obtener los caminos
más cortos entre la fuente s y todos los posibles destinos v; es por eso que los algoritmos
presentados en este capítulo resuelven este problema más general de los caminos más
cortos desde una fuente única en un gráfico dirigido.

La longitud de una ruta se define como la suma de sus pesos de arco, y la distancia de
s a v se define como la longitud de una ruta más corta entre s y v. Para simplificar la
presentación, en general mostramos solo cómo calcular la distancias. Para obtener un
camino que se dé cuenta de esta distancia, basta con mantener, además del conjunto de
distancias, un conjunto de predecesores. Por lo tanto, si dist[v] es la distancia de s a v con
dist[v] = dist[u] + w[u][v] para un vértice u, almacenamos prec[v] = u en la matriz
de predecesores . Si seguimos a los predecesores hasta el origen, podemos determinar la
ruta más corta en orden inverso, desde el origen hasta un destino determinado.

1

1. Propiedad de la composición

Los caminos más cortos exhiben una propiedad de composición, que es la clave para los
diferentes algoritmos del camino más corto. Richard Bellman llamó a esto el principio de
la optimización, que se encuentra en el corazón de los problemas de la programación
dinámica. Considere una ruta P de s a v (también conocida como ruta s - v), que pasa
por un vértice u, consulte la figura 1. Por lo tanto, es la concatenación de una ruta P1 de s
a u con una ruta P2 de u a v. La longitud de P es la suma de las longitudes de P1 y P2. Por
lo tanto, si P es una ruta más corta de s a v, entonces P1 debe ser una ruta más corta de
s a u y P2 una ruta más corta de u a v. Esto es obvio, ya que el reemplazo de P1 por una
ruta más corta daría como resultado un camino más corto de s a v.

Figura 1: Ruta más corta

Una ruta más corta de s a v que pasa por u es la concatenación de una ruta más corta de s a u con una ruta
más corta de u a v.

1.1. Vértices negros, grises y blancos

Esta propiedad de composición es la base del algoritmo de Dijkstra y sus variantes, incluso
en grafos con pesos no negativos en sus arcos. El algoritmo mantiene una matriz dist que

contiene las distancias desde la fuente hasta los vértices; se establece en +∞ para los

vértices v para los que aún no se ha encontrado ninguna ruta s - v.

Por tanto, los vértices del grafo se dividen en tres grupos, véase la figura 2. Los vértices
negros son aquellos con una ruta más corta ya identificada desde la fuente, los vértices
grises son los vecinos directos de los vértices negros y los vértices blancos son los que
actualmente no tienen una ruta más corta conocida.

Inicialmente, solo la fuente s es negra, con dist[s] = 0. Todos los vecinos directos v de
s son grises, y dist[v] es el peso del arco (s, v). Todos los demás vértices son por el
momento blancos. Luego, el algoritmo colorea repetidamente los vértices grises en negro
y sus vecinos blancos en gris, manteniendo este invariante. Finalmente, todos los vértices
alcanzables desde s serán negros, mientras que los demás permanecerán blancos.

2

Figura 2: Coloración de vértices

Ejemplo de coloración de vértices mediante el algoritmo de Dijkstra. Cada vértice v está etiquetado con
dist[v], su distancia actual desde la fuente y los arcos especificados por prec están resaltados en negrita.

1.2. Observación clave

¿Qué vértice gris deberíamos seleccionar para colorear negro? La elección se hace con un
vértice v con el menor dist[v]. ¿Por qué es esta la elección correcta? Considere una ruta
P arbitraria s-v. Dado que s es negro y v es gris, existe un primer vértice gris u en este
camino. Por lo tanto, P puede descomponerse en una ruta s − u P1 y una ruta a u − v
P2, donde P1 contiene solo vértices negros intermedios, excluyendo u. Por la elección de
v, dist[u] dist[v], y por la hipótesis de que los pesos de los arcos no son negativos, la
longitud de P2 tampoco es negativa. Por tanto, la longitud de P es al menos dist[v]. Como
la elección de P fue arbitraria, esto muestra que la ruta s - v más corta es de longitud
dist[v]. Por lo tanto, colorear v negro es válido, y para mantener el invariante, para cada
vértice v alcanzable desde v por un arco,

1.3. Estructura de datos para los vértices grises

Como para cada iteración buscamos un vértice gris v con dist[v] mínimo, una cola de prio-
ridad que contenga los vértices v es adecuada, siendo los valores de prioridad los valores
de dist. Esta es la implementación elegida para el algoritmo de Dijkstra. La eliminación
del vértice con la menor distancia se puede hacer así en el tiempo logarítmico en el número
de vértices.

Si el grafo tiene una estructura especial, entonces posiblemente se podría usar una es-
tructura más simple. Por ejemplo, en el caso de que los pesos de los arcos estén en {0,1},
solo habrá dos tipos de vértices grises, los de distancia d y los de distancia d + 1. Esta cola
de prioridad se puede implementar de una manera más sencilla utilizando una cola de dos
extremos, abreviada deque. Esta cola contiene la lista de vértices grises en orden de prio-
ridad, y basta con quitar de la izquierda en tiempo constante un vértice v para colorearlo
de negro.

3

Los vecinos de v se agregan a la cola de la izquierda o de la derecha, según si el peso en el
arco correspondiente es 0 o 1. Por último, todas las operaciones de manipulación de la cola
se pueden realizar en tiempo constante, y reducimos un factor logarítmico en comparación
con el algoritmo de Dijkstra.

Si el grafo es aún más simple, con pesos unitarios en todos sus arcos, en una forma de
decir un grafo no ponderado, entonces esta cola de dos extremos puede reemplazarse por
una cola simple y administrarse mediante el algoritmo de amplitud primero.

4

2. Gráficos con pesos 0 o 1

2.1. Definición

Dado un gráfico cuyos arcos están ponderados por 0 o 1, y un vértice fuente s, deseamos
calcular las distancias desde s hasta los otros vértices.

2.2. Aplicación

Se le proporciona un mapa de un laberinto rectangular NxM que contiene paredes que
obstruyen y le gustaría salir mientras demuele un número mínimo de paredes. El laberinto
puede verse como un gráfico dirigido cuyos arcos (de una celda a una celda adyacente)
están ponderados por 0 (acceso libre a la celda) o por 1 (acceso a una celda bloqueada
por una pared). Buscamos derribar el menor número posible de muros, lo que se reduce a
encontrar el camino más corto en este gráfico desde la entrada hasta la salida.

2.3. Algoritmo

Volvemos a la e