Menemukan jalur terpendek dan terpanjang antara dua simpul dalam DAG

Diberikan DAG tidak tertimbang (grafik asiklik langsung) $D = (V,A)$ dan dua simpul $s$ dan $t$ , apakah mungkin untuk menemukan jalur terpendek dan terpanjang dari $s$ ke $t$ dalam waktu polinomial? Panjang jalur diukur dengan jumlah tepi.

Saya tertarik menemukan kisaran panjang jalur yang mungkin dalam waktu polinomial.

Ps., Pertanyaan ini adalah duplikat dari pertanyaan StackOverflow Jalur terpanjang dalam DAG .

Untuk masalah jalur terpendek, jika kita tidak peduli dengan bobot, maka pencarian pertama yang luas adalah cara yang pasti. Kalau tidak , algoritma Dijkstra bekerja selama tidak ada tepi negatif.

Untuk jalur terpanjang, Anda selalu bisa melakukan Bellman-Ford pada grafik dengan semua bobot edge dinegasikan. Ingat bahwa Bellman-Ford bekerja selama tidak ada siklus bobot negatif, dan karenanya bekerja dengan bobot apa pun pada DAG.

Biarkan dan m = | E ( G ) | . Biarkan w ( a → b ) menunjukkan berat tepi ( a → b ) . Misalkan Anda ingin mencari biaya jalur minimum dan maksimum dari s ke t .$n = |V(G)|$$m = |E(G)|$$w(a \to b)$$(a \to b)$$s$$t$

Mulai dari , lakukan yang berikut:$b := t$

1. Jika telah dikunjungi, kembalikan min ( b ) dan maks ( b ) yang telah dihitung . Jika tidak, tandai b sebagai dikunjungi.$b$$\min(b)$$\max(b)$$b$

2. Tentukan dan catat dan maks ( b ) sebagai berikut.$\min(b)$$\max(b)$

   • Jika , simpan min ( s ) : = maks ( s ) : = 0 .$b = s$$\min(s) := \max(s) := 0$
   • Setel $$\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}$.

You should be able to prove that this algorithm runs in time $O(m)$, neglecting the time required to initialise all of the vertex variables.