Ağ gecikme süresi

Problem

1..n numaralı düğümlerden oluşan bir ağ var. times listesindeki her {u, v, w} üçlüsü, u'dan v'ye giden tek yönlü bir bağlantının sinyali w birim sürede ilettiğini söylüyor (w negatif değil). k düğümünden bir sinyal gönderiliyor. Sinyal tüm düğümlere ulaştığında ne kadar zaman geçmiş olur? Ulaşamayan bir düğüm varsa -1 döndür.

times = [{1, 2, 4}, {1, 3, 1}, {3, 2, 1}, {2, 4, 2}],  n = 4,  k = 1

1 -> 3 : 1
1 -> 3 -> 2 : 2      (doğrudan 1 -> 2 olan 4'ten kısa)
1 -> 3 -> 2 -> 4 : 4

Çıktı: 4   (en geç ulaşılan düğüm 4)

times = [{1, 2, 1}],  n = 3,  k = 1   -> -1   (3'e hiç yol yok)

Netleştirme soruları

• Kenarlar yönlü mü? (Evet.)
• Ağırlıklar negatif olabilir mi? (Hayır; bu Dijkstra'yı mümkün kılan şart. Negatif olsaydı Bellman-Ford gerekirdi.)
• Aynı iki düğüm arasında birden fazla kenar ya da kendine kenar olabilir mi?
• n ve kenar sayısı ne kadar? (Algoritma ve graf gösterimi seçimini etkiler.)
• Cevap toplam süre mi? Yani her düğüme en kısa sürenin maksimumu mu? (Evet.)

İpuçları

Yaklaşım

Cevap, tek kaynaklı en kısa yollar hesaplanıp maksimumu alınarak bulunur.

Bellman-Ford: Tüm kenarları n - 1 kez gevşet. O(V·E). Negatif ağırlıklarla da çalışır; burada gereksiz yavaştır.

Floyd-Warshall: Tüm çiftler arası en kısa yol, O(V³). Tek kaynak için israftır; testlerde referans çözüm olarak kullanıldı.

Dijkstra (seçilen çözüm): Negatif olmayan ağırlıklarda, heap'ten en küçük mesafeyle çıkan düğümün mesafesi kesinleşmiştir: ona daha kısa bir yol olsaydı, o yol heap'te daha küçük mesafeli başka bir düğümden geçmek zorunda kalırdı; ama en küçük zaten bu. Negatif kenar bu argümanı bozar.

Java'da "decrease-key" yok: PriorityQueue bir elemanın önceliğini güncellemeyi verimli desteklemez (remove(Object) O(n)). Standart çözüm lazy deletion: iyileşen düğümü yeni mesafesiyle bir kez daha ekle; heap'ten çıkan kaydın mesafesi dist'teki değerden büyükse bu eski bir kayıttır, atla. Heap en fazla E kayıt tutar.

Java çözümü

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;

public final class NetworkDelayTime {

    private record Edge(int to, int weight) {}

    /** times[i] = {from, to, weight}; düğümler 1..n; ağırlıklar negatif değil. */
    public int networkDelayTime(int[][] times, int n, int source) {
        List<List<Edge>> graph = new ArrayList<>(n + 1);
        for (int i = 0; i <= n; i++) graph.add(new ArrayList<>());
        for (int[] t : times) graph.get(t[0]).add(new Edge(t[1], t[2]));

        int[] dist = new int[n + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[source] = 0;
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[1], b[1]));  // {node, dist}
        pq.offer(new int[]{source, 0});

        while (!pq.isEmpty()) {
            int[] top = pq.poll();
            int node = top[0], d = top[1];
            if (d > dist[node]) continue;                 // bayat kayıt (lazy deletion): daha iyisi zaten işlendi
            for (Edge e : graph.get(node)) {
                int candidate = d + e.weight();
                if (candidate < dist[e.to()]) {
                    dist[e.to()] = candidate;
                    pq.offer(new int[]{e.to(), candidate});
                }
            }
        }

        int slowest = 0;
        for (int v = 1; v <= n; v++) {
            if (dist[v] == Integer.MAX_VALUE) return -1;  // ulaşılamayan düğüm
            slowest = Math.max(slowest, dist[v]);
        }
        return slowest;
    }
}

Kenar için küçük bir record kullanıldı: int[]'ten daha okunur, maliyeti ihmal edilebilir. Heap kayıtları için int[]{node, dist} tercih edildi; comparator Integer.compare kullanır. a[1] - b[1] şeklindeki çıkarma karşılaştırması büyük değerlerde taşar; mülakatta sık görülen küçük bir hata.

Karmaşıklık

• Zaman: O((V + E) log V). Her kenar en fazla bir heap ekleme yapar (O(log E) = O(log V), çünkü E ≤ V²).
• Bellek: O(V + E) komşuluk listesi ve en fazla O(E) heap kaydı.

Kenar durumlar ve testler

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

• Örnek: 4 (dolaylı yol doğrudan kenardan kısa).
• Ulaşılamayan düğüm: -1.
• Tek düğüm, kenar yok: 0.
• Sadece ters yönde kenar (2 -> 1, kaynak 1): -1; yönlülüğü test eder.
• Sıfır ağırlıklı kenar: 3.
• Paralel kenarlar (1 -> 2 ağırlık 5 ve 2): 2.
• 3.000 rastgele yönlü graf (1-8 düğüm, 0-19 kenar, 0-100 ağırlık, self-loop ve paralel kenar dahil) Floyd-Warshall referansıyla karşılaştırıldı.

Mülakatçı için

Dijkstra, büyük şirketlerin çoğunda "bilinmesi beklenen" algoritmalardandır. Ölçülen şeyler: adayın neden BFS'in yetmediğini açıklaması, Java'da decrease-key eksikliğini lazy deletion ile çözmesi, bayat kayıt kontrolünü unutmaması (unutursa sonuç yine doğrudur ama gereksiz iş yapılır) ve negatif ağırlık sınırını bilmesi.

İpucu zamanlaması: Aday BFS ile başlarsa ağırlıklı bir karşı örnek ver (doğrudan kenar 4, dolaylı yol 2). Heap fikrine 5 dakikada ulaşamazsa ikinci ipucunu ver. Dijkstra'yı bilen ama PriorityQueue'da güncelleme yapmaya çalışan adaya "bu işlem PriorityQueue'da kaç maliyetli?" diye sor.

Takip sorusu 1: Bazı kenar ağırlıkları negatif olsaydı? Beklenen: Bellman-Ford, O(V·E); n - 1 turdan sonra hâlâ gevşeyen kenar varsa negatif döngü vardır.

Takip sorusu 2: Graf yoğun (E ≈ V²) ve V = 5.000. Hangi implementasyonu seçersin? Beklenen: heap'siz O(V²) Dijkstra (her adımda dizi taraması) yoğun grafta O(E log V)'den daha hızlıdır.

Takip sorusu 3: Bir mikroservis çağrı grafında her kenar p99 gecikmesi; bir isteğin en kötü uçtan uca gecikmesini bulmak bu problemle aynı mı? Beklenen: Hayır. Paralel çağrılar ve fan-out yüzünden uçtan uca süre en kısa yol değil, çağrı ağacındaki kritik yol (DAG'de en uzun yol) gibidir; ayrıca p99'lar toplanmaz. İyi aday algoritmanın modelin varsayımlarına bağlı olduğunu görür.

Benzer problemler

• Cheapest Flights Within K Stops (LeetCode 787)
• Path with Maximum Probability (LeetCode 1514)
• Path With Minimum Effort (LeetCode 1631)
• Swim in Rising Water (LeetCode 778)
• Find the City With the Smallest Number of Neighbors at a Threshold Distance (LeetCode 1334)