Localizando caminhos mais curtos e mais longos entre dois vértices em um DAG

14

Dado um DAG não ponderado (gráfico acíclico direcionado) e dois vértices e , é possível encontrar o caminho mais curto e mais longo de para em tempo polinomial? Os comprimentos do caminho são medidos pelo número de arestas.D=(V,UMA)stst

Estou interessado em encontrar o intervalo de possíveis comprimentos de caminho em tempo polinomial.

Ps., Esta pergunta é uma duplicata da pergunta StackOverflow Caminho mais longo em um DAG .

robowolverine
fonte

Respostas:

10

Para o problema do caminho mais curto, se não nos importamos com pesos, a primeira pesquisa de largura é uma maneira infalível. Caso contrário, o algoritmo de Dijkstra funciona desde que não haja arestas negativas.

Para o caminho mais longo, você sempre pode fazer Bellman-Ford no gráfico com todos os pesos de borda negados. Lembre-se de que a Bellman-Ford funciona desde que não haja ciclos de peso negativo e, portanto, funciona com quaisquer pesos em um DAG.

jmite
fonte
2
Bellman-Ford é um algoritmo de programação dinâmica.
Raphael
1
@ Rafael sim, mas acho que existe um algoritmo DP direto para encontrar o caminho máximo, em vez de negar todos os pesos de borda.
precisa saber é
1
@jmite: Por que, é claro: apenas mudar Bellman-Ford para fazer a conversão on-line, ou maximizar, ou ...
Raphael
1
A propósito, não estou intuitivamente convencido de que o caminho mais longo do problema NP-complete esteja, portanto, facilmente em P em DAGs. Eu apreciaria uma prova / referência / explicação.
Raphael
2
Também há um algoritmo DP mais simples e eficiente para a DAG
8

Sejae. Seja denotado o peso da aresta . Suponha que você queira encontrar o custo mínimo e máximo do caminho de a .m = | E ( G ) | w ( a b ) ( a b ) s tn=|V(G)|m=|E(G)|W(umab)(umab)st

A partir de , execute o seguinte:b: =t

  1. Se já tiver sido visitado, retorne os já calculados e . Caso contrário, marque como visitado.min ( b ) max ( b ) bbmin(b)max(b)b

  2. Determine e registre e seguinte maneira.max ( b )min(b)max(b)

    • Se , armazene .mínimo ( s ) : = máximo ( s ) : = 0b=smin(s): =max(s): =0 0
    • Logo conjunto ignorando vértices para os quais . Ao calcular o mínimo e o máximo em um conjunto vazio de arestas (sem arestas de entrada para , ou todas ignoradas), defina . min(a)=max(a)=inaccessiblebmin(b):=max(b):=inacce
      min(b): =minumab[W(umab)+min(uma)]max(b): =maxumab[W(umab)+max(uma)]
      min(a)=max(a)=inaccessiblebmin(b):=max(b):=inaccessible

Você deve poder provar que esse algoritmo é executado no tempo , negligenciando o tempo necessário para inicializar todas as variáveis ​​de vértice.O(m)

Niel de Beaudrap
fonte
Essa abordagem recursiva de "puxar" pode ser realmente mais lenta que a abordagem dinâmica usual de "empurrar" e precisa de uma pilha de tamanho linear para lidar com a recursão. A abordagem usual é pegar os vértices em uma ordem topológica e melhorar o mínimo e o máximo intermediário para cada vizinho do nó atual. O nó atual sempre tem o valor final mínimo e máximo, pois todas as arestas de entrada já devem ter sido usadas para aprimorá-las.
Palec