Dijkstra e o caminho máximo

O problema do caminho mínimo é um dos problemas mais conhecidos da computação. Nesse post, vou comentar um pouco sobre o problema do caminho mínimo e também do caminho máximo, apresentando modelos de PLI para ambos. Para simplificar, vou considerar apenas as instâncias onde o grafo é direcionado e os pesos nas arestas são positivos.

O problema dos caminhos mínimos pode ser modelado como fluxo em redes. Mais especificamente, pode ser reduzido para o problema do fluxo de custo mínimo. Assim, existe naturalmente um algoritmo polinomial para resolvê-lo. Porém, da mesma forma que existem algoritmos combinatórios para o fluxo máximo e o fluxo de custo mínimo, o algoritmo de Dijkstra resolve o problema dos caminhos mínimos de maneira muito eficiente. O algoritmo foi desenvolvido por Edsger Dijkstra em 1956 tomando café em um bar. Disse o autor em uma entrevista que levou 20 minutos para desenvolver um dos algoritmos mais famosos do mundo da computação.

Claramente um algoritmo que resolva o problema dos caminhos mínimos através de programação linear não será capaz de bater a eficiência do algoritmo de Dijkstra. Mas, para fins de modelagem, vou apresentar o modelo PLI desse problema. A redução para o problema do fluxo máximo de custo mínimo é simples: basta fazer com que o fluxo máximo seja igual a 1. O modelo completo fica:

(1) Para cada nó v do grafo que não a fonte ou o sorvedouro,

(2) Para cada aresta (ij),

(3) Para cada aresta (ij),

(4)

Desta forma, temos que todo vale 0 ou 1. Devido à conservação do fluxo, as arestas com formam um caminho de s a t. Além do mais, o valor da função objetivo consiste em minimizar o custo das arestas desse caminho, justamente a definição do menor caminho.

Caminho de custo máximo

Um problema semelhante ao do caminho de menor custo é o problema do caminho de maior custo. Uma possível aplicação para esse problema é a técnica de planejamento CPM (Critical Path Method). O CPM consiste em construir um grafo direcionado com vértices correspondendo às atividades e arestas representando as dependências entre elas (ou seja, se existe uma aresta a->b, então b só pode ser executada depois que a terminar). A cada atividade está associado um custo, que é seu tempo de execução. Observe que aqui, o custo está associado a um vértice, e não a uma aresta. Isso pode ser resolvido através de uma modificação no grafo: para cada vértice v, substitua-o por vértice v’ e v’, com uma aresta v’-> v”com o custo igual ao do vértice. Para toda aresta (v,u), criamos a aresta (v”,u) e para toda aresta (u,v), criamos a aresta (u,v’) (veja a figura abaixo).

Split de um vértice para transformar custo do vértice em custo da aresta

Outra característica desse grafo é que ele é acíclico. Assim, é possível resolvê-lo em tempo polinimial através de programação dinâmica. Porém, para um grafo geral, o problema do caminho máximo é NP-completo.

Há uma característica que garante a integralidade (ou seja, que a solução do PL coincide com a do PLI) de modelos de programação linear, que é chamada de unimodularidade total. Se a matriz de coeficientes das restrições de um programa linear satisfizer certas condições, ela é dita totalmente unimodular. Isso implica que o problema que foi modelado com esse programa linear pode ser resolvido em tempo polinomial. Dois exemplos de matrizes que possuem essa estrutura são as matrizes de coeficientes dos PL’s do problema do fluxo máximo e do fluxo máximo de custo mínimo. Isso quer dizer que a matriz do PL do caminho de custo mínimo é unimodular. À primeira vista, isso parece implicar que o problema do caminho máximo pode ser resolvido em tempo polinomial, já que é só mudar a função objetivo de minimização pra maximização e, já que não modificamos a matriz de restrições, a unimodularidade total é mantida.

O problema é que não basta apenas modificar a função objetivo para que o PL resolva o problema do caminho de custo máximo. Se fizermos apenas isso, vão aparecer ciclos direcionados de custo positivo, disjuntos do caminho de s a t, já que queremos maximizar a função objetivo. Na figura abaixo, as arestas coloridas formam uma solução viável, já que ciclos (em vermelho) respeitam a conservação de fluxo. Supondo que a capacidade das arestas seja 1, o custo total da solução abaixo é 51; O maior caminho nesse grafo tem custo 33, que é maior do que o caminho encontrado em verde (ou seja, não basta jogar fora os ciclos encontrados). No problema do caminho mínimo eles não vão aparecer e por isso o modelo é válido.

Uma solução viável para o modelo com maximização

Assim, é preciso usar restrições que eliminem ciclos, o que faz com que a matriz de restrições deixe de ser totalmente unimodular. Para eliminá-los, definimos variáveis auxiliares, , associadas aos vértices. A seguinte restrição, elimina ciclos direcionados:

(5) Para cada aresta (i,j), seja M um número suficientemente grande

Se passa fluxo por uma aresta, a restrição fica,

O que implica que . Caso contrário, a desigualdade fica,

que é sempre satisfeita, tornando-a redundante.

Para ver que tal desigualdade elimina ciclos, considere um ciclo direcionado no grafo com os vértices na seguinte ordem (repeti o último vértice para explicitar que é um ciclo), corforme a figura seguinte.

Ciclo direcionado

Se houver fluxo passando por esse ciclo direcionado, a desigualdade (5) vai forçar que , ou seja , o que não pode acontecer. É fácil ver que tal desigualdade não impede a formação do caminho s-t. Basta ir atribuindo valores crescentes para u ao longo do caminho.

Uma resposta a Dijkstra e o caminho máximo

  1. […] Sometime ago, we said that problems such as the minimum path, maximum flow and minimum cost max flow can be modeled using linear programming with the interesting property that the optimal solutions are always integer. […]

%d bloggers like this: