Baixe o app para aproveitar ainda mais
Prévia do material em texto
Teoria dos Grafos Valeriano A. de Oliveira So orro Rangel Silvio A. de Araujo Departamento de Matemáti a Apli ada antunes�ibil e.unesp.br, so orro�ibil e.unesp.br, saraujo�ibil e.unesp.br AULA 5 Caminho mínimo - Algoritmo de Djskstra Preparado a partir do texto: Rangel, So orro. Teoria do Grafos, Notas de aula, IBILCE, Unesp, 2002-2013. Caminho Mínimo em Grafos Caminho Mínimo em Grafos Introduçao Caminho Mínimo em Grafos Teoria dos Grafos (Antunes Rangel&Araujo) � 3 Considere a rede: s t a b cd 9 15 4 2 2 3 35 16 6 5 7 21 Caminho Mínimo em Grafos Teoria dos Grafos (Antunes Rangel&Araujo) � 4 Dado dois vérti es nesta rede, queremos determinar o menor aminho entre eles. Uma primeira questão é omo representar os valores asso iados às arestas neste grafo. Isto pode ser feito através da matriz de pesos. Seja D um digrafo simples ujas arestas possuem �pesos� asso iados, digamos, a ada aresta (vi, vj) está asso iado um número real wij ≥ 0 (que pode representar omprimento, distân ia, valor, et ). Vamos de�nir wii = 0 para todo i e wij =∞ quando não existe uma aresta entre os vérti es vi e vj . Assim a matriz de pesos é uma matriz n× n de�nida omo W = [wij], onde n é o número de vérti es. Exemplo Caminho Mínimo em Grafos Teoria dos Grafos (Antunes Rangel&Araujo) � 5 Construir a matriz de pesos para a rede abaixo: s t a b cd 9 15 4 2 2 3 35 16 6 5 7 21 Caminho Mínimo em Grafos Teoria dos Grafos (Antunes Rangel&Araujo) � 6 Observação 1. Em geral ■ wij 6= wji e ■ wij + wjk pode ser menor ou igual a wik. Por exemplo, na rede anterior, wsd + wda = 9 + 4 ≤ 15 = wsa. O algoritmo que nós vamos ver foi proposto por Dijkstra em 1959 e é um dos mais e� ientes até hoje. Vamos supor então que queremos en ontrar o aminho mínimo entre e na rede a ima. Caminho Mínimo em Grafos Teoria dos Grafos (Antunes Rangel&Araujo) � 6 Observação 2. Em geral ■ wij 6= wji e ■ wij + wjk pode ser menor ou igual a wik. Por exemplo, na rede anterior, wsd + wda = 9 + 4 ≤ 15 = wsa. • O algoritmo que nós vamos ver foi proposto por Dijkstra em 1959 e é um dos mais e� ientes até hoje. Vamos supor então que queremos en ontrar o aminho mínimo entre s e t na rede a ima. Idéia do Algoritmo: Caminho Mínimo em Grafos Teoria dos Grafos (Antunes Rangel&Araujo) � 7 ■ Rotular os vérti es do digrafo. ■ A partir do vérti e ini ial s, pro eder em direção ao vérti e �nal t (seguindo as arestas orientadas) rotulando os vérti es om as suas distân ias ao vérti e s, medida até aquele momento. ■ A ada estágio do algoritmo teremos vérti es que possuem rótulos temporários e outros rótulos permanentes. ■ O rótulo de um vérti e vj é feito permanente quando este rótulo representa a menor distân ia de s até vj. ■ Começamos asso iando rótulo permanente igual a zero para o vérti e s, e um rótulo temporário igual a ∞ para os outros n− 1 vérti es do grafo. ■ A ada iteração, um novo vérti e re ebe um rótulo permanente de a ordo om as seguintes regras: Caminho Mínimo em Grafos Teoria dos Grafos (Antunes Rangel&Araujo) � 8 1. Cada vérti e vj om um rótulo temporário, re ebe um novo rótulo temporário dado por: min{rótulo de vj, (rótulo de vi) + wij} onde vi é o vérti e que re ebeu rótulo permanente na iteração anterior e wij é o valor da aresta entre o vérti e vi e o vérti e vj. 2. En ontre o menor valor entre os rótulos temporários. Este será o rótulo permanente do respe tivo vérti e. Em aso de empate sele ione qualquer um dos andidatos e atribua rótulo permanente ao es olhido. � Repetir 1 e 2 até que o vérti e destino, t, re eba um rótulo permanente. Exemplo Caminho Mínimo em Grafos Teoria dos Grafos (Antunes Rangel&Araujo) � 9 Vamos apli ar a ideia a ima à rede abaixo: s t a b cd 9 15 4 2 2 3 35 16 6 5 7 21 Apli ação do algoritmo: Caminho Mínimo em Grafos Teoria dos Grafos (Antunes Rangel&Araujo) � 10 Ini ializaçao: rot(s) = 0 é permanente, rot(a) = rot(b) = rot(c) = rot(d) = rot(t) =∞ são temporários it = 1 Regra 1 � Novo rótulo Novo rot(a) = min{∞, 0 + wsa} = min{∞, 15} = 15 Novo rot(b) = min{∞, 0 + wsb} = min{∞,∞} =∞ Novo rot(c) = min{∞, 0 + wsc} = min{∞,∞} =∞ Novo rot(d) = min{∞, 0 + wsd} = min{∞, 9} = 9 Novo rot(t) = min{∞, 0 + wst} = min{∞,∞} =∞ Regra 2 � Rótulo permanente min{15,∞,∞, 9,∞} = 9 ⇒ rot(d) torna-se permanente Apli ação do algoritmo ont.: Caminho Mínimo em Grafos Teoria dos Grafos (Antunes Rangel&Araujo) � 11 it = 2 Regra 1 � Novo rótulo Novo rot(a) = min{15, 9 + wda} = min{15, 9 + 4} = 13 Novo rot(b) = min{∞, 9 + wdb} = min{∞,∞} =∞ Novo rot(c) = min{∞, 9 + wdc} = min{∞, 9 + 2} = 11 Novo rot(t) = min{∞, 9 + wdt} = min{∞,∞} =∞ Regra 2 � Rótulo permanente min{13,∞, 11,∞} = 11 ⇒ rot(c) torna-se permanente Regra 1 � Novo rótulo Novo Novo Novo Regra 2 � Rótulo permanente torna-se permanente Apli ação do algoritmo ont.: Caminho Mínimo em Grafos Teoria dos Grafos (Antunes Rangel&Araujo) � 11 it = 2 Regra 1 � Novo rótulo Novo rot(a) = min{15, 9 + wda} = min{15, 9 + 4} = 13 Novo rot(b) = min{∞, 9 + wdb} = min{∞,∞} =∞ Novo rot(c) = min{∞, 9 + wdc} = min{∞, 9 + 2} = 11 Novo rot(t) = min{∞, 9 + wdt} = min{∞,∞} =∞ Regra 2 � Rótulo permanente min{13,∞, 11,∞} = 11 ⇒ rot(c) torna-se permanente it = 3 Regra 1 � Novo rótulo Novo rot(a) = min{13, 11 + wca} = min{13, 11 +∞} = 13 Novo rot(b) = min{∞, 11 + wcb} = min{∞, 11 +∞} =∞ Novo rot(t) = min{∞, 11 + wct} = min{∞, 11 + 7} = 18 Regra 2 � Rótulo permanente min{13,∞, 18} = 13 ⇒ rot(a) torna-se permanente Apli ação do algoritmo ont.: Caminho Mínimo em Grafos Teoria dos Grafos (Antunes Rangel&Araujo) � 12 it = 4 Regra 1 � Novo rótulo Novo rot(b) = min{∞, 13 + wab} = min{∞, 13 + 35} = 48 Novo rot(t) = min{18, 13 + wat} = min{18, 13 +∞} = 18 Regra 2 � Rótulo permanente min{48, 18} = 18 ⇒ rot(t) torna-se permanente Fim Podemos parar pois o vérti e destino, , re ebeu rótulo permanente. Assim o menor aminho entre e tem omprimento igual a 18. Como re uperar o aminho? A partir do vérti e destino , veri� amos o vérti e om rótulo permanente usado na obtenção do rótulo de . No nosso exemplo, o vérti e . Repetimos o pro esso a partir de até al ançar o vérti e ini ial . Assim temos . O aminho é obtido invertendo a ordem obtida: . Apli ação do algoritmo ont.: Caminho Mínimo em Grafos Teoria dos Grafos (Antunes Rangel&Araujo) � 12 it = 4 Regra 1 � Novo rótulo Novo rot(b) = min{∞, 13 + wab} = min{∞, 13 + 35} = 48 Novo rot(t) = min{18, 13 + wat} = min{18, 13 +∞} = 18 Regra 2 � Rótulo permanente min{48, 18} = 18 ⇒ rot(t) torna-se permanente Fim Podemos parar pois o vérti e destino, t, re ebeu rótulo permanente. Assim o menor aminho entre s e t tem omprimento igual a 18. Como re uperar o aminho? A partir do vérti e destino t, veri� amos o vérti e om rótulo permanente usado na obtenção do rótulo de t. No nosso exemplo, o vérti e c. Repetimos o pro esso a partir de c até al ançar o vérti e ini ial s. Assim temos t, c, d, s. O aminho é obtido invertendo a ordem obtida: s, d, c, t. Implementação Caminho Mínimo em Grafos Teoria dos Grafos (Antunes Rangel&Araujo) � 13 Em uma possível implementação deste algoritmo vamos pre isar armazenar as seguintes informações: ■ Indi ação se um vérti e vk possui rótulo permanente ou temporário. ■ Guardar a menor distân ia entre o vérti e ini ial s e o vérti e vk.■ Guardar o vérti e om rótulo permanente que deu origem a um novo rótulo (importante para re uperar o aminho). Assim vamos podemos de�nir a seguinte estrutura de dados: 1. Entrada de Dados: Matriz de pesos W (O(n2)). 2. A di� uldade é distinguir, a ada iteração, os vérti es om rótulos permanentes e os vérti es om rótulo temporário. Utilizamos um vetor lógi o (ou binário) n-dimensional: final(v) = { True se o rótulo do vérti e v é permanente, False se o rótulo do vérti e v é temporário. Caminho Mínimo em Grafos Teoria dos Grafos (Antunes Rangel&Araujo) � 14 3. Pre isamos também de um vetor n-dimensional para guardar as distân ias a umuladas do vérti e ini ial s ao vérti e vk. Vamos hamar este vetor de dist. 4. Como re uperar o aminho? Sabemos que a menor distân ia será dada por dist(t). Mas qual é este aminho? Cada vez que o rótulo de um vérti e é modi� ado pre isamos saber a partir de que vérti e foi al ulado o novo rótulo. Mantendo um vetor n-dimensional pred tal que: • pred(v) indi a o vérti e om rótulo permanente que deu origem ao rótulo do véti e v, • e se v for o vérti e ini ial, então pred(s) = −1; temos que o menor aminho é dado por: s, pred(pred(· · · )), . . . , pred(pred(t)), pred(t), t. Caminho Mínimo em Grafos Teoria dos Grafos (Antunes Rangel&Araujo) � 15 Considere um digrafo D(V,A), om n vérti es e sua matriz de pesos W = [wij ], n× n. Queremos en ontrar o menor aminho entre o vérti e s e o vérti e t no digrafo D. De�na os vetores: ■ final(i) � indi a se o vérti e vi re ebeu rótulo permanente (poten ial) ou não; ■ dist(i) � indi a a distân ia a umulada do vérti e ini ial s até o vérti e vi; ■ pred(i) � indi a o vérti e om rótulo permanente que deu origem ao rótulo do véti e vi. Algoritmo de Dijkstra Caminho Mínimo em Grafos Teoria dos Grafos (Antunes Rangel&Araujo) � 16 Ini ialização para todo v ∈ V faça iní io dist(v) =∞ final(v) = falso pred(v) = −1 �m dist(s) = 0 final(s) = verdadeiro recente = s Algoritmo de Dijkstra ont. Caminho Mínimo em Grafos Teoria dos Grafos (Antunes Rangel&Araujo) � 17 Iteração Prin ipal enquanto final(t) = falso faça iní io para todo vérti e vj tal que exista a aresta (recente, vj) e tal que final(j) = falso faça iní io (atualização dos rótulos) rotulo = dist(recente) + wrecente,j (o rótulo de vj é modi� ado se houver um aminho menor de s a vj através do vérti e re ente) se rotulo < dist(j) então iní io dist(j) = rotulo pred(j) = recente �m �m (en ontre o vérti e om menor rótulo temporário) Seja y o vérti e om menor rótulo temporário, tal que dist(y) 6=∞ iní io (o rótulo do vérti e y se torna permanente) final(y) = verdadeiro recente = y �m �m Exemplo Caminho Mínimo em Grafos Teoria dos Grafos (Antunes Rangel&Araujo) � 18 Rastrear o algoritmo de Dijkstra usando o digrafo om vérti es s, a, b, c, d, t uja matriz de pesos asso iada é: W = 0 7 4 9 7 ∞ 7 0 1 ∞ ∞ 6 4 1 0 3 ∞ ∞ 9 ∞ 3 0 1 3 7 ∞ ∞ 1 0 5 ∞ 6 ∞ 3 5 0 . Exemplo ont. Caminho Mínimo em Grafos Teoria dos Grafos (Antunes Rangel&Araujo) � 19 Ini ialização dist = [∞ ∞ ∞ ∞ ∞ ∞] final = [falso falso falso falso falso falso] pred = [−1 − 1 − 1 − 1 − 1 − 1] dist(s) = 0 final(s) = verdadeiro recente = s it = 1 Vérti es v tais que existe a aresta (recente, v) e tais que final(v) = falso: a, b, c, d Exemplo ont. Caminho Mínimo em Grafos Teoria dos Grafos (Antunes Rangel&Araujo) � 20 v = a: rotulo = dist(recente) + wrecente,a = 0 + 7 <∞ = dist(a) dist(a) = 7 pred(a) = s v = b: rotulo = dist(recente) + wrecente,b = 0 + 4 <∞ = dist(b) dist(b) = 4 pred(b) = s v = c: rotulo = dist(recente) + wrecente,c = 0 + 9 <∞ = dist(c) dist(c) = 9 pred(c) = s v = d: rotulo = dist(recente) + wrecente,d = 0 + 7 <∞ = dist(d) dist(d) = 7 pred(d) = s Exemplo ont. Caminho Mínimo em Grafos Teoria dos Grafos (Antunes Rangel&Araujo) � 21 Vérti e y om menor rótulo temporário, tal que dist(y) 6=∞: b final(b) = verdadeiro recente = b Vérti es tais que existe a aresta e tais que : : : Exemplo ont. Caminho Mínimo em Grafos Teoria dos Grafos (Antunes Rangel&Araujo) � 21 Vérti e y om menor rótulo temporário, tal que dist(y) 6=∞: b final(b) = verdadeiro recente = b it = 2 Vérti es v tais que existe a aresta (recente, v) e tais que final(v) = falso: a, c v = a: rotulo = dist(recente) + wrecente,a = 4 + 1 < 7 = dist(a) dist(a) = 5 pred(a) = b v = c: rotulo = dist(recente) + wrecente,c = 4 + 3 < 9 = dist(c) dist(c) = 7 pred(b) = b Exemplo ont. Caminho Mínimo em Grafos Teoria dos Grafos (Antunes Rangel&Araujo) � 22 Vérti e y om menor rótulo temporário, tal que dist(y) 6=∞: a final(a) = verdadeiro recente = a Vérti es tais que existe a aresta e tais que : : Vérti e om menor rótulo temporário, tal que : ou Exemplo ont. Caminho Mínimo em Grafos Teoria dos Grafos (Antunes Rangel&Araujo) � 22 Vérti e y om menor rótulo temporário, tal que dist(y) 6=∞: a final(a) = verdadeiro recente = a it = 3 Vérti es v tais que existe a aresta (recente, v) e tais que final(v) = falso: t v = t: rotulo = dist(recente) + wrecente,t = 5 + 6 <∞ = dist(t) dist(t) = 11 pred(t) = a Vérti e y om menor rótulo temporário, tal que dist(y) 6=∞: c ou d final(c) = verdadeiro recente = c Exemplo ont. Caminho Mínimo em Grafos Teoria dos Grafos (Antunes Rangel&Araujo) � 23 it = 4 Vérti es v tais que existe a aresta (recente, v) e tais que final(v) = falso: d, t v = d: rotulo = dist(recente) + wrecente,d = 7 + 1 ≮ 7 = dist(d) v = t: rotulo = dist(recente) + wrecente,t = 7 + 3 < 11 = dist(t) dist(t) = 10 pred(t) = c Vérti e y om menor rótulo temporário, tal que dist(y) 6=∞: d final(d) = verdadeiro recente = d Exemplo ont. Caminho Mínimo em Grafos Teoria dos Grafos (Antunes Rangel&Araujo) � 24 it = 5 Vérti es v tais que existe a aresta (recente, v) e tais que final(v) = falso: t v = t: rotulo = dist(recente) + wrecente,d = 7 + 5 ≮ 7 = dist(d) Vérti e y om menor rótulo temporário, tal que dist(y) 6=∞: t final(t) = verdadeiro recente = t Como final(t) = verdadeiro, pare Exemplo omt. Caminho Mínimo em Grafos Teoria dos Grafos (Antunes Rangel&Araujo) � 25 Qual é o valor do menor aminho? dist(t) = 10 Qual é este aminho? t, pred(t) t, c, pred(c) t, c, b, pred(b) t, c, b, s, pred(s) t, c, b, s,−1 O menor aminho é {s, b, c, t} Exemplo ont. Caminho Mínimo em Grafos Teoria dos Grafos (Antunes Rangel&Araujo) � 26 E se quisermos o menor aminho entre s e c? Podemos aproveitar os ál ulos anteriores. Como c possui rótulo permanente, temos que: dist(c) = 7 E o aminho é: c, pred(c) c, b, pred(b) c, b, s O menor aminho é então: {s, b, c}. Observações Caminho Mínimo em Grafos Teoria dos Grafos (Antunes Rangel&Araujo) � 27 1. A omplexidade em termos de tempo omputa ional do algoritmo a ima é dada por: O laço prin ipal deste algoritmo, no pior aso, é exe utado n− 1 vezes. Isto a onte e quando o vérti e �nal, t, é o último a re eber um rótulo permanente. Para ada exe ução deste laço, pre isamos examinar uma linha da matriz de pesos, e atualizar os vetores dist e pred, ou seja um tempo propor ional a n. Assim o tempo total é da ordem 2n(n− 1). A omplexidade é O(n2). Observe que independe do número de arestas no grafo. 2. É possível, usando o algoritmo de Dijkstra en ontrar o menor aminho entre o vérti e s e todos os outros vérti es do grafo.O que deve ser modi� ado? Observações Caminho Mínimo em Grafos Teoria dos Grafos (Antunes Rangel&Araujo) � 28 1. Outros Algoritmos para problemas de Caminho Mínimo em grafos podem ser en ontrados por exemplo na página 283 de: [Otimização Combinatória e Programação Linear, M.C. Goldbarg e H.P.L. Luna, Ed. Campus, 2000℄. 2. O algoritmo de Dijskstra fun iona apenas se wij ≥ 0 para todos i, j. Veri�que este fato apli ando o algoritmo à seguinte rede para en ontrar o menor aminho entre v1 e v3: v1 v2 v3 1 -5 5 Caminho Mínimo em Grafos Introduçao Exemplo Idéia do Algoritmo: Exemplo Aplicação do algoritmo: Aplicação do algoritmo cont.: Aplicação do algoritmo cont.: Implementação Algoritmo de Dijkstra Algoritmo de Dijkstra cont. Exemplo Exemplo cont. Exemplo cont. Exemplo cont. Exemplo cont. Exemplo cont. Exemplo cont. Exemplo comt. Exemplo cont. Observações Observações
Compartilhar