En fazla k aktarmayla en ucuz uçuş

Problem

0..n-1 numaralı n şehir ve tek yönlü uçuşlar var; her uçuş {from, to, price}. src şehrinden dst şehrine en fazla k ara durakla (yani en fazla k + 1 uçuşla) gidilebilecek en ucuz fiyatı döndür. Böyle bir rota yoksa -1.

Uçuşlar: 0->1: 100, 1->2: 100, 2->3: 100, 0->3: 500, 0->2: 300
src = 0, dst = 3

k = 0  (sadece direkt)        -> 500
k = 1  (en fazla 1 aktarma)   -> 400   (0 -> 2 -> 3)
k = 2                         -> 300   (0 -> 1 -> 2 -> 3)

Uçuşlar: 0->1: 10, 1->2: 10;  src = 0, dst = 2, k = 0   -> -1

Netleştirme soruları

• "k durak" ara şehir sayısı mı, uçuş sayısı mı? (Ara şehir; uçuş sayısı en fazla k + 1.)
• Fiyatlar pozitif mi? Aynı iki şehir arasında birden fazla uçuş olabilir mi?
• src == dst olabilir mi? (Olursa cevap 0.)
• n, uçuş sayısı ve k ne kadar büyük? (Seçilecek algoritmanın karmaşıklığı k'ya bağlı.)
• Rotayı da döndürmem gerekiyor mu, sadece fiyat mı?

İpuçları

Yaklaşım

Neden düz Dijkstra yetmez: Dijkstra her düğüm için tek bir "en iyi" değer tutar. Burada bir şehre ucuz ama çok aktarmalı ulaşmak, pahalı ama az aktarmalı ulaşmaktan her zaman iyi değildir; çünkü az aktarmalı yol, kalan aktarma hakkıyla hedefe ulaşabilir. Durum (şehir) yerine (şehir, kullanılan uçuş sayısı) olmalıdır.

Kaba çözüm: src'den derinliği k + 1 ile sınırlı DFS ile tüm rotaları dene. Dallanma faktörü b ise O(b^(k+1)); testlerde referans olarak kullanıldı.

Sınırlı Bellman-Ford (seçilen çözüm): cost[v] = "şu ana kadarki tur sayısı kadar uçuşla v'ye en ucuz fiyat". Her tur tüm uçuşları bir kez gevşetir ve izin verilen uçuş sayısını bir artırır. k + 1 tur sonunda cost[dst] cevaptır. Kopya dizi (next) şarttır: güncelleme sadece önceki turun değerlerinden yapılmalıdır. Bu aslında bir DP'dir: dp[i][v] = min(dp[i-1][v], min over (u,v,w) of dp[i-1][u] + w), sadece iki satır tutulur.

Alternatifler: (1) Durumu (şehir, uçuş sayısı) olan Dijkstra; heap'ten çıkan ilk dst kaydı cevaptır, ama aynı şehir farklı uçuş sayılarıyla tekrar işlenmelidir. (2) Katman bazlı BFS; her katman bir uçuş, maliyet iyileşirse kuyruğa ekle. Üçü de doğrudur; Bellman-Ford en kısa ve en kolay kanıtlananıdır.

Java çözümü

import java.util.Arrays;

public final class CheapestFlights {

    private static final int UNREACHABLE = Integer.MAX_VALUE;

    /** flights[i] = {from, to, price}; en fazla k ara durak = en fazla k + 1 uçuş. */
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        int[] cost = new int[n];
        Arrays.fill(cost, UNREACHABLE);
        cost[src] = 0;

        for (int round = 0; round <= k; round++) {       // her tur: "bir uçuş daha" serbest
            int[] next = cost.clone();                   // bu turda sadece ÖNCEKİ turun değerlerinden genişlet
            for (int[] f : flights) {
                int from = f[0], to = f[1], price = f[2];
                if (cost[from] == UNREACHABLE) continue;
                if (cost[from] + price < next[to]) next[to] = cost[from] + price;
            }
            cost = next;
        }
        return cost[dst] == UNREACHABLE ? -1 : cost[dst];
    }
}

UNREACHABLE kontrolü olmadan Integer.MAX_VALUE + price taşar ve negatif bir sayı "çok ucuz" görünür. Bu, en kısa yol kodlarında en sık görülen Java hatasıdır.

Karmaşıklık

• Zaman: O(k · E); k + 1 tur, her turda tüm uçuşlar, ve her turda O(n) kopya: toplam O(k · (n + E)).
• Bellek: O(n) iki maliyet dizisi. Komşuluk listesi bile gerekmez; kenar listesi doğrudan kullanılır.

Kenar durumlar ve testler

Testler main içinde çalıştırıldı:

• Örnek graf: k = 1 için 400, k = 2 için 300, k = 0 için 500.
• Aktarma gerekli ama k = 0: -1.
• src == dst: 0.
• Zincir 0 -> 1 -> 2 -> 3, k = 1: -1. Kopya dizi kullanılmasaydı, tek turda zincir boyunca ilerleyip yanlışlıkla 3 dönebilirdi; bu test o hatayı yakalar.
• 2.000 rastgele graf (2-7 şehir, k = 0..3), derinlik sınırlı DFS kaba çözümüyle karşılaştırıldı.

Mülakatçı için

Bu soru, adayın ezberlediği bir algoritmayı (Dijkstra) kısıt altında sorgulayıp sorgulamadığını ölçer. Visited kümeli klasik Dijkstra yazan aday yanlış sonuç üretir; bunu fark ettirmek için şu örneği ver: 0->1 ucuz, 0->2->1 daha da ucuz ama iki uçuş, 1->3 var, k = 1.

Gözlemlenecek ikinci şey kopya dizinin gerekçesidir: aday kopyayı "ezberden" yazdıysa nedenini sor.

İpucu zamanlaması: Aday Dijkstra'yı kısıtsız uygularsa önce karşı örnekle dry run iste. 5-6 dakika içinde durum genişletme ya da Bellman-Ford fikrine ulaşamazsa ikinci ipucunu ver. Kopya dizi hatasını yaparsa zincir testini öner.

Takip sorusu 1: En ucuz rotanın kendisini döndür. Beklenen: her tur için parent dizisi tutmak (tur başına, çünkü en iyi öncül uçuş sayısına göre değişir) ve dst'den geri izlemek.

Takip sorusu 2: n = 10.000, E = 100.000, k = 5.000. Hangi yaklaşım? Beklenen: Bellman-Ford O(k·E) = 5×10⁸ yavaş kalabilir; durumlu Dijkstra'da (şehir, uçuş sayısı) çiftlerini budamak (bir şehre daha az uçuşla daha ucuza ulaşıldıysa o durumu atla) pratikte çok daha hızlıdır.

Takip sorusu 3: Gerçek bir uçuş arama servisinde başka hangi kısıtlar olur? Beklenen: zaman pencereleri (aktarma süresi, kalkış saatleri; graf zamana bağlı olur), çok kriterli optimizasyon (fiyat + süre + aktarma; Pareto cephesi), önbellekleme ve önceden hesaplanmış popüler rotalar.

Benzer problemler

• Network Delay Time (LeetCode 743)
• Minimum Cost to Reach Destination in Time (LeetCode 1928)
• Path With Minimum Effort (LeetCode 1631)
• Number of Ways to Arrive at Destination (LeetCode 1976)
• Shortest Path in a Grid with Obstacles Elimination (LeetCode 1293)