Am:ağırlıklı grafiği ve bu bağlantı bir soru çözmeye çalıştığı bütün çift yol
(Bu ödev soru değildir)
n ile bir ağırlıklı çizge G dikkate köşeler ve e kenarları ve ağırlıklar tamsayılardır. G'nin hiçbir negatif döngü içermediğini ve G'deki u ve v her bir çift tepe noktası için, u'dan v'ye olan mesafenin, bazı pozitif tamsayılar için [-2d, 2d] aralığında düştüğünü varsayalım. G'deki belirli bir kenarı (x, y) düzelteceğiz ve bu kenarla ilişkili ağırlığı değiştirdiğimiz için G'deki mesafelere ne olacağını düşünelim (ve diğer tüm kenar ağırlıklarını sabit bırakıyoruz).
G'yi giriş olarak G'nin yanı sıra belirtilen bir kenarı (x, y) alan bir algoritma tasarlayın. Algoritmanın çıktısı, bu kenarın ağırlığına (x, y) ait bir değer aralığı olmalıdır. G'deki tüm mesafeler aynı kalacaktı. Bu aralığın kenar boşluğunun orijinal ağırlığını (x, y) içermesi gerektiği için boş olmayacağını unutmayın. Ayrıca, sonsuzluğun aralığınızın bir son noktası olarak da görülebileceğini unutmayın (yani aralık sonlu olmayabilir). Bunun için “∞” değerini bir son nokta olarak gönderebilirsiniz. Algoritmanızın çalışma süresi n, e ve d cinsinden polinom olmalıdır (böylece çalışma sürenizde bu parametrelerden herhangi birinin üsler olarak görünmemesi gerekir). Algoritmanın neden doğru olduğunu kanıtlayın.
Aşağıdaki satırlarda düşünüyordum: mesafelerin aralığında olan yana, ağırlıklar aynı zamanda bir aralıkta olmalıdır. Bir seçenek Djkstra'nın birden çok kez çalıştırılmasıdır. Bunu nasıl optimize ederiz?
Bu grafikte negatif kenar ağırlıkları var, Djikstra'nın algoritması çalışmayacak. – moreON
@moreON Evet, negatif kenarlar varsa Dijkstra çalışmayacak. – HenryLee
Ve soru açıkça negatif kenar ağırlıklarının olduğunu belirtir. – moreON