İndirimli yollarla en kısa yollar
Görev tanımı
Problem
Bir bölgede 0'dan n - 1'e kadar numaralanmış n kasaba ve [u, v, cost] biçiminde tek yönlü yollar var. Bazı yollar indirim ödüyor, yani maliyetleri negatif; ama hiçbir yol döngüsünün toplamı negatif değil. src kasabasından her kasabaya en ucuz maliyeti döndür; ulaşılamayan kasabalar için None kullan.
Örnekler
Input: n = 4, roads = [[0, 1, 4], [0, 2, 5], [2, 1, -3], [1, 3, 2]], src = 0
Output: [0, 2, 5, 4]
Neden: 0'dan 2'ye, oradan 1'e gitmek 5 - 3 = 2 tutar; 4 tutan 1'e doğrudan yoldan ucuz
Input: n = 3, roads = [[0, 1, -2]], src = 0
Output: [0, -2, None]
Neden: 2 numaralı kasabaya giden yol yok
Input: n = 1, roads = [], src = 0
Output: [0]
Neden: edge case: başlangıç kasabasına ulaşmak hiçbir şeye mal olmaz
İpuçları
0 / 3
İlk örnekte 1 numaralı kasaba, 2 numaralı kasabadan geçen indirimli yol görülmeden 4 maliyetle kesinleşmiş gibi görünüyor. Bu, alışılmış en ucuzdan başlama yaklaşımını neden bozuyor?
Bir yolu gevşetmek, başlangıç kasabası üzerinden gitmek daha ucuzsa bitiş kasabasının maliyetini düşürmek demektir. En ucuz bir yolun en fazla n - 1 yolu vardır ve yollar üzerindeki her tam geçiş, her en ucuz yolun en az bir yolunu daha sabitler.
src dışında her maliyeti sonsuza ayarla. n - 1 kez tekrarla: her yolu gevşet. Bütün bir geçiş hiçbir şeyi değiştirmezse erken dur. Hâlâ sonsuz olan maliyetleri None'a çevir.
- Hedef zaman
- O(n · m)
- Hedef alan
- O(n)
Kısıtlar
- towns are numbered 0 to n - 1
- road costs may be negative
- no loop of roads has a negative total
Çözüm
Bellman-Ford, yeterince geçiş çalışana kadar hiçbir maliyete güvenmez. k. geçişten sonra en ucuz yolu en fazla k yol kullanan her kasabanın maliyeti kesindir, çünkü o yolun son yolu, sondan ikinci kasabası zaten doğruyken gevşetilmiştir. Hiçbir döngünün toplamı negatif değilken en ucuz bir yol asla bir kasabayı tekrarlamaz; bu yüzden n - 1 geçiş yeter, değişiklik olmayan bir geçiş de her maliyetin zaten kesin olduğu anlamına gelir. En ucuzdan başlayan arama burada başarısız olur, çünkü sonradan bulunan indirimli bir yol zaten kesinleştirdiği bir kasabanın altına inebilir. m yol için zaman O(n · m), alan O(n).
def cheapest_from(n, roads, src):
INF = float("inf")
cost = [INF] * n
cost[src] = 0
for _ in range(n - 1): # a cheapest path uses at most n - 1 roads
changed = False
for u, v, c in roads:
if cost[u] != INF and cost[u] + c < cost[v]:
cost[v] = cost[u] + c # relax the road
changed = True
if not changed: # nothing moved: every cost is final
break
return [x if x != INF else None for x in cost]
print(cheapest_from(4, [[0, 1, 4], [0, 2, 5], [2, 1, -3], [1, 3, 2]], 0)) # -> [0, 2, 5, 4]
print(cheapest_from(3, [[0, 1, -2]], 0)) # -> [0, -2, None]
print(cheapest_from(1, [], 0)) # -> [0]Kodda değil de fikirde mi takıldın? Bellman-Ford bunu anlatıyor.