Ruta más Corta con una sóla Fuente de Inicio (Single-Source Shortest Paths) 1 DR. JESÚS A. GONZÁLEZ BERNAL CIENCIAS COMPUTACIONALES INAOE

Problema de Encontrar la Ruta más Corta 2

y Se requiere llegar de la ciudad A a la ciudad B y Tenemos un mapa con distancias entre cada par de

intersecciones y ¿Cómo encontramos la ruta más corta? {

{

Enumerar todas las rutas de A a B, calcular la distancia y elegir la más corta Aún si quitamos ciclos, hay muchas posibilidades

y Resolver el problema eficientemente

Problema de Encontrar la Ruta más Corta 3

y Tenemos un grafo dirigido y con pesos G = (V, E) y Con una función de pesos w: E Æ R que mapea arcos

e pesos con valores reales y El peso de la ruta p = es la suma de los pesos de los arcos que la forman: k

w( p ) = ∑ w(vi −1 , vi ) i =1

Problema de Encontrar la Ruta más Corta 4

y Definimos el peso de la ruta más corta de u a v como p ⎧min{w( p ) : u ⎯ ⎯→ v} Si hay una ruta de u a v, δ (u, v) = ⎨ de cualquier otra forma ⎩∞

y Una Ruta-más-corta de un vértice v a un vértice u se

define como cualquier ruta p con peso w(p) = δ(u,v)

Modelado del Problema 5

y Podemos modelarlo con un grafo { Los vértices representan intersecciones { Los arcos representan segmentos de carretera entre intersecciones { Los pesos de los arcos representan las distancias en carretera y La meta es encontrar la ruta más corta de una ciudad A

a otra ciudad B {

Los pesos también pueden representar otras métricas Ù

Tiempo, costo, pérdidas, castigos, u otra cantidad que se acumula linealmente a lo largo de la ruta y que queremos minimizar

Variantes del Problema 6

y Problema de las rutas más cortas desde una sola

fuente {

Dado un grafo G = (V, E), queremos encontrar la ruta más corta de un vértice fuente dado s ∈ V a cada vértice v ∈ V.

y Problema de las rutas más cortas con un solo

destino {

Encontrar una ruta más corta a un vértice destino dado t de cada vértice v. Si invertimos la dirección de cada arco en el grafo, podemos reducir este problema al de una sola fuente.

Variantes del Problema 7

y Problema de la ruta más corta para un solo par { Encontrar la ruta más corta de u a v para los vértices u y v dados. { Si resolvemos el problema de una sola fuente con el vértice u como fuente también resolvemos éste. { No se conoce un algoritmo para este problema que corra asintóticamente más rápido que el mejor algoritmo de una sola fuente en el peor caso

Variantes del Problema 8

y Problema de las rutas más cortas de todos los pares { Encontrar una ruta más corta de u a v para cada par de vértices u y v. { Aunque este problema se puede resolver ejecutando un algoritmo de una sola fuente, una vez para cada vértice, se puede resolver más rápido

Subestructura Óptima de una Ruta más Corta 9

y Los algoritmos de rutas más cortas se basan en la

propiedad de que una ruta más corta entre dos vértices contiene otra ruta más corta en ella y Esta propiedad permite aplicar { {

Programación dinámica (Floyd-Warshall) Algoritmos voraces (Dijkstra’s)

Subestructura Óptima de una Ruta más Corta 10

y Lema 24.1 (Subrutas de rutas más cortas son rutas

más cortas) {

{

{

{

Dado un grafo pesado y dirigido G = (V, E) con una función de peso w: E Æ R Sea p = una ruta más corta del vértice v1 al vértice vk y Para cualquier i y j tal que 1 ≤ i ≤ j ≤ k, sea pij = la subruta de p del vértice vi al vértice vj Entonces pij es una ruta más corta de vi a vj

Subestructura Óptima de una Ruta más Corta 11

y Prueba al lema 24.1 { Descomponemos la ruta p en: { Tenemos entonces que: { Asumimos que hay una ruta p’ij de vi a vj con peso: { Entonces la ruta de v1 a vk que pasa por p’ij: { Con peso: { Tiene un peso menor a w(p) { Contradice lo que asumimos, que p es una ruta más corta de v1 a vk.

p1i pij pjk v1 ⎯⎯→ vi ⎯⎯→ v j ⎯⎯→ vk

w( p ) = w( p1i ) + w( pij ) + w( p jk )

w( p 'ij ) < w( pij ) p1i p 'ij pjk v1 ⎯⎯→ vi ⎯⎯→ v j ⎯⎯→ vk

w( p1i ) + w( p 'ij ) + w( p jk )

Representación de las Rutas más Cortas 12

y Utilizamos un grafo de predecesores Gπ = (Vπ, Eπ) {

π[v] denota al padre del vértice v

y Al final el grafo de predecesores es un “árbol de rutas más

cortas” {

y

Un árbol con raíz que contiene una ruta más corta de la fuente s a cada vértice que es alcanzable desde s.

Un árbol de rutas más cortas con raíz s es un subgrafo dirigido G’ = (V’, E’), donde V’ ⊆ V y E’ ⊆ E tal que: { { {

V’ es el conjunto de vértices alcanzable desde s en G G’ forma un árbol con raíz s y Para cada v ∈ V’, la única ruta simple de s a v en G’ es una ruta más corta de s a v en G

Representación de las Rutas más Cortas 13

y Las rutas más cortas no son necesariamente únicas { Tampoco los árboles de rutas más cortas

Técnica de Relajación (Relaxation) 14

y Estos algoritmos utilizan la técnica de relajación y Para cada vértice v ∈ V, mantenemos un atributo

d[v], una frontera superior del peso de la ruta más corta desde la fuente s a v y A d[v] se le llama un estimado de ruta más corta

Técnica de Relajación (Relaxation) 15

y Inicialización

Técnica de Relajación (Relaxation) 16

y Relajación de un arco (u, v) consiste en { Probar si podemos mejorar la ruta más corta a v encontrada a través de u y si es posible, actualizar d[v] y π[v] y El proceso puede decrementar el valor de la estimación

de la ruta más corta d[v] y actualizar el predecesor π[v]

Técnica de Relajación (Relaxation) 17

Técnica de Relajación (Relaxation) 18

y Los lemas 24.10, 24.11, 24.14, 24.15 y 24.17 y el

corolario 24.12 muestran como relajando después de INITIALIZE-SINGLE-SOURCE, se alcanzará el peso de la ruta más corta y el grafo de predecesores será un árbol de rutas más cortas {

Asumimos que no hay ciclos con peso negativo

Algoritmo Bellman-Ford 19

y Resuelve el problema de rutas más cortas desde una

sola fuente { {

En el caso general puede haber arcos con pesos negativos Dado un grafo dirigido, con pesos, con fuente s y función de pesos w : E Æ R, regresa un valor booleano indicando si hay o no un ciclo con peso negativo que es alcanzable desde la fuente Si existe un ciclo de este tipo, el algoritmo indica que no hay solución Ù Si no hay un ciclo de este tipo, el algoritmo produce las rutas más cortas y sus pesos Ù

Algoritmo Bellman-Ford 20

y El algoritmo utiliza el proceso de relajación y Progresivamente decrementa un estimado d[v] sobre

el peso de una ruta más corta de la fuente s a cada vértice v ∈ V hasta que llega al peso real de la ruta más corta δ(s,v)

Algoritmo Bellman-Ford 21

Algoritmo Bellman-Ford 22

y Primero inicializa, línea 1 y Hace |V|-1 pasadas sobre los arcos, loop líneas 2-4 { Relaja cada arco del grafo una vez y Checa si hay un ciclo con peso negativo, líneas 5-8 { Si hay regresa FALSE { Si no hay regresa TRUE y Tiempo de ejecución { O(VE) Inicialización Θ(V) Ù Cada pasada (V-1 en total) por las líneas 2-4 Θ(E) Ù Ciclo líneas 5-7 O(E) Ù

Algoritmo Bellman-Ford 23

Algoritmo Bellman-Ford 24

Algoritmo Bellman-Ford 25

y Teorema 24.4 (el algoritmo de Bellman-Ford es

correcto) {

{

Si ejecutamos Bellman-Ford en un grafo dirigido, pesado G = (V,E) con fuente s y función de pesos w: E ÆR. Si G no contiene ciclos con peso negativo que sean alcanzables desde s Entonces el algoritmo regresa TRUE Ù Tenemos d[v] = δ(s,v) para todos los vértices v ∈ V Ù El subgrafo de predecesores Gπ es un árbol de rutas más cortas con s como raíz . Ù

{

Si G contiene un ciclo con peso negativo, alcanzable desde s Ù

Entonces el algoritmo regresa FALSE

Rutas más Cortas desde una sola Fuente en Grafos Dirigidos Acíclicos (DAG) 26

y Relajamos los arcos de un dag pesado, G = (V,E) de

acuerdo a un ordenamiento topológico de sus vértices {

{ {

Calculamos las rutas más cortas desde una sola fuente en tiempo Θ(V + E) Las rutas más cortas siempre están bien definidas en un dag Aún si hay arcos con pesos negativos, no puede existir un ciclo con peso negativo

Rutas más Cortas desde una sola Fuente en Grafos Dirigidos Acíclicos (DAG) 27

y Tiempo de ejecución total: Θ(V + E) y Ordenamiento topológico: Θ(V + E) y Llamada a Initialize-Single-Source: Θ(V) y Loop líneas 3-5: Θ(E)

Rutas más Cortas desde una sola Fuente en Grafos Dirigidos Acíclicos (DAG) 28

y El algoritmo primero ordena topológicamente el dag

para poner un orden en los vértices y Si hay una ruta de u a v, entonces u precede a v en el orden topológico y Se hace una pasada sobre los vértices ordenados topológicamente y Cada que se procesa un vértice, se relaja cada arco que sale del vértice

Rutas más Cortas desde una sola Fuente en Grafos Dirigidos Acíclicos (DAG) 29

Rutas más Cortas desde una sola Fuente en Grafos Dirigidos Acíclicos (DAG) 30

Rutas más Cortas desde una sola Fuente en Grafos Dirigidos Acíclicos (DAG) 31

y Aplicación { Diagramas de Pert (program evaluation and review technique)

Algoritmo de Dijkstra 32

y Resuelve el problema de rutas más cortas desde una

sola fuente con un grafo dirigido y pesado G = (V, E) para el caso en que los pesos no son negativos y Asumimos que w(u,v) > 0 para cada arco (u,v) ∈ E

Algoritmo de Dijkstra 33

Algoritmo de Dijkstra 34

y Mantiene un conjunto S de vértices para los cuales se y y y y

ha determinado la ruta más corta desde la fuente s Después selecciona un vértice u ∈ V – S con el estimado mínimo de ruta más corta Añade u a S y relaja todos los arcos de salen de u La implementación usa un Priority-Queue de vértices utilizando como llave los valores d También mantiene el padre que llevó a la ruta más corta hasta ese momento, π[v]

Algoritmo de Dijkstra 35

Algoritmo de Dijkstra 36

Algoritmo de Dijkstra 37

Algoritmo de Dijkstra 38

y Es un algoritmo voraz { Porque siempre elige el vértice más ligero o más cercano en V – S para añadir al conjunto S { Dijkstra’s calcula rutas más cortas { Cada vez que se añade un vértice u al conjunto S, tenemos que d[u] = δ(s,u).

Algoritmo de Dijkstra 39

y Teorema 24.6 (El algoritmo de Dijkstra es correcto) { El algoritmo de Dijkstra, ejecutado sobre un grafo pesado y dirigido G = (V, E) con una función de pesos no-negativos w y una fuente s, termina con d[u] = δ(s,u) para todos los vértices u ∈ V. y Corolario 24.7 { Si ejecutamos el algoritmo de Dijkstra sobre un grafo pesado y dirigido G = (V, E) con una función de pesos no-negativos w y una fuente s, entonces a la terminación, el subgrafo de predecesores Gπ es un árbol de rutas más cortas con s como raíz.

TAREA 40

y Hacer una prueba de ciclo invariante para el

algoritmo de Dijkstra