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

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,A)$$s$$t$$s$$t$

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 .

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.

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 $n = |V(G)|$$m = |E(G)|$$w(a \to b)$$(a \to b)$$s$$t$

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 ) $b$$\min(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 ) : = $b = s$$\min(s) := \max(s) := 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):=inacc $$\begin{align*}\min(b) &:= \min_{a \to b} \Bigl[ w(a \to b) + \min(a) \Bigr] \\ \max(b) &:= \max_{a \to b} \Bigl[ w(a \to b) + \max(a) \Bigr]\end{align*}$$ $\min(a) = \max(a) = \mathrm{inaccessible}$$b$$\min(b) := \max(b) := \mathrm{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)$