Notas de Aula: Teoria dos Grafos - Caminhos Mínimos

Centro de Matemática Computação e Cognição Universidade Federal do ABC Profa Carla Negri Lintzmayer Notas de aula da disciplina Teoria dos Grafos Esse material é um compilado dos seguintes Sedgewick R Algorithms in C part 5 graph algorithms 3rd ed AddisonWesley 2002 Bondy J A Murty U S R Graph Theory Graduate Texts in Mathematics Springer New York 2008 Lintzmayer C N Mota G O Notas de aulas Análise de algoritmos e estruturas de dados Em construção 12 Aulas 16 e 17 caminhos minimos e Seja G um digrafo com custos nas arestas dados por w EG R De forma geral dado um subdigrafo H C G denotamos por wH o valor decnH We denominado custo de H Particularmente 0 custo wP de um caminho P vj v2U 6 a soma dos custos das arestas de P isto é wP yo wviVj41 e Definimos a distdéncia ponderada entre u ev denotada distéu v como sendo o custo de um wvcaminho de menor custo ou oo se nao houver uvcaminho e Dizemos que um caminho de menor custo cujo custo é igual a distancia é um caminho minimo Um stcaminho minimo nao é necessariamente tnico e Exemplo no digrafo da esquerda um 5 8caminho minimo tem custo 4 e no digrafo da direita tem custo 7 3 3 0 0 8 1 vv 9 8 1 2 9 11 9 1 5 6 6 1 p 1 3 7 10 6 3 4 ay a 9 e Existem basicamente trés variagoes de problemas de caminhos minimos PROBLEMA DO CAMINHO MiNIMO DE UNICO DESTINO Entrada digrafo G w EG Re vértices st VG Objetivo calcular distst e Algoritmos classicos que 0 resolvem A tempo OE log V 74 Problema do Caminho Mínimo de Única Fonte Entrada digrafo G w EG R e vértice s V G Objetivo calcular distw Gs v para todo v V G Algoritmos clássicos que o resolvem BFS se we wf para toda e f EG tempo OV E DFS se G é um DAG tempo OV E Dijkstra 1959 se we 0 para toda e EG tempo OE log V BellmanFord 1956 tempo ΘV E Problema do Caminho Mínimo entre Todos os Pares Entrada digrafo G w EG R Objetivo calcular distw Gu v para todo par u v V G Algoritmos clássicos que o resolvem FloydWarshall 1962 tempo ΘV 3 Johnson 1977 tempo ΘV E log V Observações Algoritmos para o problema do Caminho Mínimo entre Todos os Pares certa mente resolvem os outros dois problemas Algoritmos para o problema do Caminho Mínimo de Única Fonte podem ser usados para resolver o problema do Caminho Mínimo entre Todos os Pares executeos uma vez para cada vértice sendo fonte Alguns tempos de execução podem ser melhorados em grafos Melhor algoritmo para todos os pares tempo OV 3 log log V log2 V Han Takaoka 2014 75 121 Grafos digrafos e custos negativos Algoritmos que lidam com problemas de encontrar distâncias em digrafos não funcionam corretamente quando o grafo possui arestas com pesos negativos ou o digrafo possui ciclos com pesos negativos Com o que se sabe até o momento em Ciência da Computação não é possível existir um algoritmo eficiente que resolva problemas de distância nessas situações O problema de caminhos mínimos em digrafos com ciclos de custo negativo é NPdifícil Lembrese que dado um grafo G seu digrafo associado é o digrafo DG com con junto de vértices V DG V G e u v EG se e somente se u v EDG e v u EDG Se G é um grafo com custos nas arestas dados por uma função w então podemos dar custos aos arcos de DG com uma função w tal que wuv wvu wuv Note que caminhos mínimos em G são caminhos mínimos em DG e vice versa Se G tem uma aresta com wuv 0 então u v u é um ciclo de custo negativo em DG Se conseguirmos resolver o problema em qualquer tipo de digrafo que não tenha ciclo negativo então conseguiremos resolvêlo em particular para digrafos que são digrafos associados de grafos 122 Princípios genéricos de algoritmos para Caminhos Mínimos Teorema 121 Seja D um digrafo e w ED R tal que D não tem ciclo negativo Se P v0 v1 vk é um v0vkcaminho mínimo então vi vi1 vj é um vivj caminho mínimo para qualquer 0 i j k Lema 122 Seja D um digrafo e w ED R tal que D não tem ciclo negativo Dados u v V D se Q é um uvpasseio em D então existe um uvcaminho P tal que wP wQ 76 123 Caminhos Mínimos de Única Fonte Os algoritmos manterão para cada vértice u V D distu para armazenar o custo de um sucaminho encontrado pelo algoritmo estimativa de distância predu para armazenar o predecessor de u no sucaminho encontrado pelo algoritmo Relaxar uma aresta xy significa verificar se é possível utilizála para melhorar a estimativa de distância até y 1 Função Relaxax y 2 Se distx wxy disty então Cuidado Se distx 3 disty distu wxy 4 predy x Cuidados de implementação Matematicamente c para toda constante c R Mas e quando for INTMAX ou DOUBLEMAX E quando c 0 Os algoritmos sempre inicializam dists 0 e distv para todo v V Ds O resultado a seguir mostra que eles sempre vão ter em distv uma estimativa de distância que é pelo menos o valor da distância real Proposição 123 Seja D um digrafo w ED R e s V D um vértice qual quer Se D não possui ciclos de custo negativo então um algoritmo que modifica dist apenas por meio de relaxações sempre vai manter distx distw Ds x para todo x V D Demonstração Vamos provar por indução em k que após k relaxações nós temos distx distw Ds x para todo x V D Quando k 0 nenhuma relaxação ocorreu De fato neste momento temos dists 0 distw Ds s 0 e distx distw Ds x para todo x s Agora suponha k 0 e considere que a késima relaxação será da aresta uv 77 Neste momento apenas distv tem chances de ser modificado de forma que após a relaxação já podemos afirmar que distx distw Ds x para todo x v Ademais como antes da relaxação já sabemos que distv distw Ds v precisamos mostrar que essa relação se mantém apenas se distv muda Logo podemos considerar que distv distu wuv após a relaxação Como um sucaminho mínimo seguido do arco uv é um svpasseio vale que distw Ds v distw Ds u wuv Já sabíamos que distu distw Ds u Juntando as inequações temos distw Ds v distw Ds u wuv distu wuv distv de onde vemos que se mantém distv distw Ds v O teorema a seguir nos ajuda a provar mais facilmente a corretude de alguns desses algoritmos Teorema 124 Seja D um digrafo ponderado por w ED R tal que D não tem ciclo negativo Seja s V D e dist um vetor indexado pelos vértices tal que para todo v V D vale que 1 distv é o custo de algum svcaminho caso exista 2 distv se não há svcaminho 3 dists 0 Para todo v V D distv distw Ds v se e somente se todo arco de D não pode ser relaxado Demonstração Primeiro vamos mostrar que se para todo v V D distv distw Ds v então todo arco de D não pode ser relaxado Suponha para fins de contradição que existe um arco xy ED que pode ser relaxado isto é tal que distx wxy disty Assim podemos assumir que distx e portanto existe um sxcaminho P tal que wP distx Seja Q construído a partir de P in serindo o vértice y ao final Note que Q é um sypasseio tal que wQ wPwxy Pelo Lema 122 existe um sycaminho Q tal que wQ wQ Assim wQ wP wxy distx wxy disty distw Ds v o que é um absurdo 78 Agora vamos provar que se todo arco de D nao pode ser relaxado entao distv distsv para todo v VD Seja x VD Se nao ha sacaminho em D sabemos por hipdtese que dista co dists x e o resultado nesse caso segue Entao suponha que ha szcaminho em D Seja P vp U1U um szcaminho minimo em D isto é wP distsx Como todo arco de D nao pode ser relaxado entao sabemos que distv distu1 wviivi parai12k Somando as k expressoes acima note que temos k distuz distug S wvi10i dists wP 0 wP disths x i1 Como por hipdtese distv distz é o custo de um sxcaminho em D s6 pode ser o caso de termos distxz dists x como queriamos O 1231 Algoritmo para DAGs e Esse algoritmo simplesmente percorre os vértices do grafo de acordo com uma or denagao topoldogica relaxando todos os arcos que saem do vértice 1 Fungao CAMMINUNIFONDAGD w s 2 Para cada v VD faga 3 predv 1 4 distv oo 5 predis s 6 dists 0 7 S ORDENATOPOLOGICAD S v1Un 8 Para i 1 até VD faga 9 Para cada x Nv faga 10 RELAXAv e Ele claramente leva tempo OV E OV no laco de inicializagéo OV EF na ordenagao topologica OV EF no lago da relaxacao Teorema 125 Seja D um DAG w ED Res VD um vértice qualquer O algoritmo CAMMINUNIFONDAGD w s resolve 0 problema do Caminho Minimo de Unica Fonte em digrafos actclicos 79 Demonstração Primeiro note que todo arco xy ED é relaxado exatamente uma vez quando x vi para algum i 1 k Logo após isso teremos distxwxy disty o que continuará válido até o fim da execução disty só pode reduzir devido a relaxações de outros arcos zy e distx não mudará devido à ordenação topológica Então pelo Teorema 124 distv distw Ds v para todo v V D 1232 Algoritmo de Dijkstra A ideia do algoritmo de Dijkstra é similar à dos algoritmos de busca e ao algoritmo de Prim vamos crescer uma arborescência a partir de um vértice inicial que no caso é o vértice s dado na entrada do problema Essa arborescência conterá svcaminhos mínimos para todo v para os quais existe caminho a partir de s Inicialmente nenhum vértice está visitado s tem estimativa de distância dists 0 e todos os outros vértices têm estimativa de distância distv A cada iteração um vértice não visitado x é escolhido para ser visitado momento a partir do qual distx e predx não mudarão mais Neste momento todos os arcos que saem de x são relaxados A forma como Dijkstra faz para escolher o próximo vértice x a ser visitado é gulosa escolhese o vértice que naquele momento tem a menor estimativa de distância dentre os não visitados Perceba que em nenhum momento o algoritmo de Dijkstra verifica se o digrafo de entrada possui arcos de peso negativo De fato ele encerra sua execução normalmente Acontece porém que ele não calcula os pesos dos caminhos mínimos corretamente 80 1 Função DijkstraD w s 2 Para cada v V D faça 3 predv 1 4 distv 5 visitadov 0 6 dists 0 7 preds s 8 Enquanto houver vértice u com visitadou 0 faça 9 seja x um vértice não visitado com menor valor distx 10 visitadox 1 11 Para cada y N x faça 12 Relaxax y Teorema 126 Seja D um digrafo w ED R0 e s V D um vértice qual quer O algoritmo DijkstraD w s resolve o problema do Caminho Mínimo de Ùnica Fonte Demonstração Vamos denotar por distiv o valor em distv na iésima iteração do laço enquanto Note que distiv distjv para qualquer v V D e j i pois só mudamos estimativas de distância quando elas diminuem por meio de relaxação Note ainda que qualquer arco de D é relaxado exatamente uma vez no momento em que sua cauda é visitada Agora fixe um arco xy ED qualquer e vamos mostrar que ao final da execução xy não poderá ser relaxado Suponha que x é visitado na késima iteração Assim logo após visitarmos x teremos distkx wxy distky Assim se em alguma iteração ℓ k tivermos distℓx wxy distℓy deve ser porque distx mudou e não disty Formalmente visitamos algum vértice z e relaxamos o arco zx de forma que distℓz wzx distℓx distkx Mas note que na késima iteração escolhemos x porque distkx distkv para todo v V D não visitado Particularmente z não estava visitado de forma que distkx distkz o que implica que distkx distℓz Se tivermos distkx distℓz então como distℓz distkz teríamos distkx distkz o que não é 81 verdade Mas então usando a inequação acima e o fato que wzx 0 temos distℓz distℓz wzx distkx distℓz o que é um absurdo Então nenhum arco pode ser relaxado ao final da execução de forma que pelo Teorema 124 distv distw Ds v para todo v V D ao final Podemos fazer uma implementação direta do algoritmo apresentado que a todo momento busca pelo menor valor armazenado no vetor dist Inicializar os vértices leva tempo OV o laço enquanto irá executar OV vezes a linha 9 irá executar OV vezes com cada execução levando tempo OV e analisar todas arestas que saem de um vértice x leva tempo Odx sendo que fazemos isso para todos os vértices Assim o algoritmo leva tempo OV 2 E ao todo Porém note que a operação mais custosa é a que procura pelo menor valor no vetor dist e conhecemos uma estrutura de dados muito boa para fazer isso Podemos fazer uso de uma Heap binária Todos os vértices não visitados devem estar na Heap A prioridade de um vértice v é o valor em distv multiplicado por 1 já que quanto menor o valor em dist maior a prioridade do vértice Assim RemoveDaHeap devolve o próximo vértice que deve ser visitado Com isso o tempo de execução passa a ser OE log V São OV chamadas iniciais ao InsereNaHeap cada uma com tempo Olog V São OV chamadas ao RemoveDaHeap cada uma com tempo Olog V São OE chamadas ao Relaxa que por sua vez chama o AlteraHeap que leva tempo Olog V Então o tempo total é OV E log V que é OE log V quando E V 82 1 Função RelaxaDijkstrax y 2 Se distx wxy disty então Cuidado 3 disty distu wxy 4 predy x 5 AlteraHeapH v distv 1 Função DijkstraD w s 2 Seja Q uma Heap 3 Para cada v V D faça 4 predv 1 5 distv 6 InsereNaHeapH v distv 7 dists 0 8 preds s 9 AlteraHeapH s 0 10 Enquanto Q faça 11 x RemoveDaHeapQ 12 Para cada y N x faça 13 RelaxaDijkstrax y 1233 Algoritmo de BellmanFord O algoritmo de BellmanFord resolve o problema dos Caminhos Mínimos de Única Fonte mesmo quando os arcos do digrafo de entrada têm peso negativo Mais ainda quando existe um ciclo de peso total negativo o algoritmo identifica a existência de tal ciclo A ideia principal é tentar em V D 1 iterações melhorar a estimativa de dis tância conhecida a partir de s para todos os vértices v analisando todos os arcos de D em cada iteração O número V D 1 não é mágico qualquer caminho em um digrafo tem no máximo V D 1 arestas A intuição por trás dessa ideia é garantir que dado um svcaminho mínimo o algoritmo relaxe os arcos desse caminho em ordem 83 1 Fungao QUASEBELLMANFORDD w s 2 Para cada v VD faga 3 predv 1 4 distv 00 5 dists 0 6 preds s 7 Para i 1 até VD faga 8 Para cada xy ED faga 9 RELAXAz y Lema 127 Seja D um digrafo w ED Res VD um vértice qual quer Se D nao possui ciclos de custo negativo entao ao final da execucao de QUASEBELLMANFORDD w s para todo v VD vale que 1 distv 00 se nao ha svcaminho 2 distv distsv se ha svcaminho 3 dists 0 Demonstragaéo Seja v VD tal que nao ha svcaminho isto é distsv oo Pela Proposigéo 123 sabemos que distv oo Como nao é possivel distv 00 so podemos ter distv oo Agora seja v VD tal que ha svcaminho isto é distsv 4 oo Seja P Up U1U U um svcaminho minimo Vamos provar por indugéo em 7 que distv i wv1v ao final da iésima iteracaéo do laco para da linha 7 Se 7 0 nenhuma iteragao ocorreu Note que dists 0 e de fato a1 wvj1 0 Agora seja i 0 e suponha por hipdtese de inducgao que logo apos a i 1ésima iteracao distv a wv1v Durante a iésima iteracgao o algoritmo relaxa todas as arestas de D em particular vv Entao assim que essa aresta for relaxada temos distv distv1 wui1u 0 que implica i1 i distv distluj1 wviivi S wvj10j wvj1Ui S wvj10 jl jl Concluimos entaéo que distu uv distsv apds a késima iteracao Pela Proposigao 123 sabemos que distv distsv também Logo s6 pode ser 0 caso 84 de distv distw Ds v Como o laço executa V 1 vezes e k V 1 o resultado segue Por fim note que dists 0 antes do segundo laço para começar e que se esse valou mudou ao final é porque dists 0 já que só modificamos dist por meio de relaxações Mas pela Proposição 123 só podemos ter dists 0 Logo de fato dists 0 ao fim Mas e com relação a ciclos de custo negativo Teorema 128 Seja D um digrafo e w ED R Se C é um ciclo de custo negativo em D então C contém um arco que pode ser relaxado Por causa do teorema acima depois das V D 1 iterações o algoritmo ainda verifica uma última vez se há arestas que podem ser relaxadas A seguir temos a versão completa do algoritmo de BellmanFord que devolve V erdadeiro quando funciona e Falso quando não funciona 1 Função BellmanFordD w s 2 Para cada v V D faça 3 predv 1 4 distv 5 dists 0 6 preds s 7 Para i 1 até V D 1 faça 8 Para cada xy ED faça 9 Relaxax y 10 Para cada xy ED faça 11 Se distx wxy disty então arco xy pode ser relaxado 12 Devolve Falso 13 Devolve V erdadeiro Teorema 129 Seja D um digrafo w ED R e s V D um vértice qualquer Se D não possui ciclos com custo negativo então o algoritmo BellmanFordD w s resolve o problema do Caminho Mínimo de Ùnica Fonte e devolve V erdadeiro Caso contrário o algoritmo devolve Falso Demonstração Primeiro suponha que D não tem ciclos com custo negativo Vamos 85 provar que distv distw Ds v para todo v V D ao final e que o algoritmo devolve V erdadeiro Pelo Lema 127 sabemos que ao final do laço para da linha 7 vale que distv distw Ds v para qualquer v V D Então o Teorema 124 nos permite concluir que nenhum arco pode ser relaxado o que implica que a condição da linha 10 não será satisfeita e o algoritmo devolverá V erdadeiro Suponha agora que D tem ciclos com custo negativo Neste caso por causa do Teorema 128 sabemos que quando o último laço para executar certamente algum arco xy poderá ser relaxado fazendo com que a condição da linha 10 seja verdadeira e o algoritmo devolverá Falso Note que o primeiro laço leva tempo OV o segundo laço leva tempo OV E e o último laço leva tempo OE de forma que o tempo total do algoritmo de BellmanFord é OV E 124 Caminhos Mínimos entre Todos os Pares Os algoritmos manterão para cada par de vértices u v V D distuv para armazenar o custo de um uvcaminho encontrado pelo algo ritmo preduv para armazenar o predecessor de v no uvcaminho encontrado pelo algoritmo 1241 Algoritmo de FloydWarshall O algoritmo de FloydWarshall calcula xycaminhos mínimos por meio de relaxações de caminhos isto é verificando se é possível utilizar um novo vértice v para melhorar a estimativa de distância entre x e y 1 Função Relaxax y v 2 Se distxv distvy distxy então Cuidado Se distxv 3 distxy distxv distvy 4 predxy predvy Nesta seção vamos considerar que V D 1 2 V 86 1 Função QuaseFloydWarshallD w 2 Para k 1 até V faça 3 Para i 1 até V faça 4 Para j 1 até V faça 5 Relaxai j k Defina Vk 1 2 k Assim V0 Vamos definir um Vkcaminho como sendo um caminho cujos vértices internos estão em Vk apenas Por exemplo no digrafo a seguir todos os V5caminhos entre 3 e 8 são 3 5 1 4 8 e 3 5 4 8 Todos os V6caminhos entre 3 e 8 são 3 5 1 4 8 3 5 4 8 e 3 5 6 8 Não existem V4caminhos entre 3 e 8 Vamos definir dk ij como sendo o custo de um Vkcaminho mínimo entre i e j 3 5 1 4 8 é um V6caminho mínimo entre 3 e 8 e d6 3 8 6 1 2 3 4 5 6 7 8 9 10 8 3 4 0 9 9 5 11 2 3 4 1 6 0 Teorema 1210 Seja D um digrafo e w ED R tal que D não tem ciclo de custo negativo Para qualquer par i j V D vale que dk ij 0 se k 0 e i j wij se k 0 e ij ED se k 0 e ij ED mindk1 ij dk1 ik dk1 kj se k 0 Demonstração O resultado claramente vale quando k 0 Vamos considerar então que k 1 Seja P um Vkcaminho mínimo entre i e j então wP dk ij Note que há apenas 87 duas possibilidades k V P ou k V P Se k V P então observe que os vértices internos de P estão em Vk1 De fato podemos afirmar que P é um Vk1caminho mínimo entre i e j Se não fosse haveria um Vk1caminho mínimo P entre i e j tal que wP wP que claramente é uma contradição pois P é um Vkcaminho entre i e j Neste caso concluímos que wP dk1 ij Se k P então P i k j pode ser dividido em dois caminhos P1 i k e P2 k j Note que P1 é um Vk1caminho entre i e k e P2 é um Vk1caminho entre k e j De fato podemos afirmar que P1 é um Vk1caminho mínimo entre i e k e P2 é um Vk1caminho mínimo entre k e j Se P1 não fosse um tal caminho então haveria um Vk1caminho mínimo P 1 entre i e k tal que wP 1 wP1 de forma que P 1 seguido de P2 seria um Vkpasseio entre i e j de custo menor do que wP e que conteria um Vkcaminho entre i e j de custo possivelmente ainda menor Lema 122 o que é uma contradição O mesmo vale se P2 não fosse um tal caminho Neste caso concluímos que wP dk1 ik dk1 kj 1 Função FloydWarshallD w 2 Para i 1 até V faça 3 predii i 4 distii 0 5 Para j 1 até V faça 6 Se ij ED então 7 predij i 8 distij wij 9 Senão 10 predij 1 11 distij 12 Para k 1 até V faça 13 Para i 1 até V faça 14 Para j 1 até V faça 15 Relaxai j k 16 Para i 1 até V faça 17 Se distii 0 então 18 Devolve Falso 19 Devolve V erdadeiro 88 Teorema 1211 Seja D um digrafo e w ED R Se D não tem ciclos de custo negativo então ao final da execução do laço para da linha 12 temos distij dV ij Demonstração Provaremos por indução em k que após a késima iteração do laço para da linha 12 temos distij dk ij para todo par i j V D Isso implica diretamente no resultado desejado Se k 0 então não houve ainda iteração do laço e de fato temos distij d0 ij para todo par i j V D Suponha então k 1 e suponha que distuv dk1 uv para todo par u v V D Note que durante a execução o algoritmo faz distij mindistij distik distkj Como por hipótese distij dk1 ij antes da mudança distik dk1 ik e distkj dk1 kj então o resultado segue devido ao Teorema 1210 Teorema 1212 Seja D um digrafo e w ED R Seja dist a matriz construída pelo algoritmo de FloydWarshall quando executado sobre D w Existe distii 0 se e somente se D possui um ciclo com custo negativo Teorema 1213 Seja D um digrafo w ED R Se D não possui ciclos com custo negativo então o algoritmo FloydWarshallD w resolve o problema do Caminho Mínimo entre Todas as Fontes e devolve V erdadeiro Caso contrário o algoritmo devolve Falso Demonstração Primeiro suponha que D não tem ciclos com custo negativo Então pelo Teorema 1211 sabemos que ao final da execução do laço para da linha 12 temos distij distw Di j O Teorema 1212 nos permite concluir que distii 0 para todo i V D o que significa que a condição da linha 17 não será satisfeita e o algoritmo devolverá V erdadeiro Suponha agora que D tem ciclos com custo negativo Nesse caso o Teorema 1212 nos permite concluir que existe algum i V D tal que distii 0 o que significa que a condição da linha 17 será satisfeita e o algoritmo irá devolver Falso Note que o primeiro laço leva tempo OV 2E OV 2 o segundo laço leva tempo OV 3 e o último laço leva tempo OV de forma que o tempo total do algoritmo de FloydWarshall é OV 3 89