Menemukan jalur terpendek di hadapan siklus negatif

13

Diberikan grafik siklik terarah di mana bobot setiap sisi mungkin negatif, konsep "jalur terpendek" hanya masuk akal jika tidak ada siklus negatif, dan dalam hal ini Anda dapat menerapkan algoritma Bellman-Ford.

Namun, saya tertarik untuk menemukan jalur terpendek antara dua simpul yang tidak melibatkan siklus (mis. Di bawah batasan bahwa Anda mungkin tidak mengunjungi simpul yang sama dua kali). Apakah masalah ini dipelajari dengan baik? Bisakah varian dari algoritma Bellman-Ford digunakan, dan jika tidak, apakah ada solusi lain?

Saya juga tertarik dengan masalah semua pasangan yang setara, yang untuknya saya mungkin menerapkan Floyd-Warshall.

ds.algorithms graph-algorithms shortest-path jleahy
sumber

Jawaban:

23

Jalur tanpa simpul berulang disebut jalur sederhana , jadi Anda mencari jalur sederhana terpendek dalam grafik dengan siklus negatif.

Ini dapat dikurangi dari masalah jalur terpanjang . Jika ada pemecah cepat untuk masalah Anda, maka berikan grafik dengan hanya bobot tepi positif, meniadakan semua bobot tepi dan menjalankan pemecah Anda akan memberikan jalur terpanjang dalam grafik asli.

Dengan demikian masalah Anda adalah NP-Hard.

BlueRaja - Danny Pflughoeft
sumber
1
Ini jawaban yang indah. Saya sudah bertanya kepada beberapa orang tentang IRL ini tanpa solusi apa pun dan ketika saya menjelaskan hal ini kepada mereka, reaksi mereka sama dengan reaksi saya - "tentu saja, saya merasa sangat bodoh sekarang".
jleahy