Menemukan jalur terpendek dan terpanjang antara dua simpul dalam DAG

14

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 .

robowolverine
sumber

Jawaban:

10

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.

Ya ampun
sumber
2
Bellman-Ford adalah algoritma pemrograman yang dinamis.
Raphael
1
@ Raphael ya, tapi saya pikir ada algoritma DP langsung untuk menemukan jalur max, bukannya meniadakan semua bobot tepi.
jmite
1
@jmite: Mengapa, tentu saja: ganti saja Bellman-Ford untuk melakukan konversi secara online, atau maksimalkan, atau ...
Raphael
1
Ngomong-ngomong, saya tidak yakin secara intuitif bahwa masalah NP-complete Path terpanjang demikian mudah dalam P pada DAGs. Saya menghargai bukti / referensi / penjelasan.
Raphael
2
Juga ada algoritma DP yang lebih sederhana dan efisien untuk DAG
8

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(ab)(ab)st

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.bmin(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=smin(s):=max(s):=0
    • Setel
      min(b):=minab[w(ab)+min(a)]max(b):=maxab[w(ab)+max(a)]
      min(a)=max(a)=inaccessiblebmin(b):=max(b):=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.

Niel de Beaudrap
sumber
Pendekatan "tarikan" rekursif ini mungkin sebenarnya lebih lambat dari pendekatan "dorong" dinamis yang biasa dan perlu tumpukan ukuran linier untuk menangani rekursi. Pendekatan yang biasa adalah mengambil simpul dalam urutan topologi dan meningkatkan minimum sementara dan maksimum untuk setiap tetangga dari simpul saat ini. Node saat ini selalu memiliki nilai akhir minimum dan maksimum karena semua tepi masuk harus sudah digunakan untuk memperbaikinya.
Palec