Network Delay Time

Q: Berapa kompleksitas waktu Network Delay Time?

Dengan algoritma Dijkstra dan binary heap, kompleksitas waktunya adalah O(E log E) , dengan E sebagai jumlah tautan. Nilai itu sama dengan O(E log n) , karena E paling banyak n². Kompleksitas ruangnya adalah O(n + E) . Bellman-Ford membutuhkan waktu O(n · E) .

Q: Mengapa algoritma Dijkstra membutuhkan bobot yang tidak negatif?

Dijkstra tidak pernah mengunjungi kembali node yang sudah ditetapkan, yang aman hanya jika tidak ada rute berikutnya yang lebih singkat. Dengan jalur A → B berdurasi 2, A → C berdurasi 3, dan C → B berdurasi -2, algoritma ini menetapkan B pada 2, tetapi rute melalui C mencapainya pada 1. Bellman-Ford menangani durasi negatif.

Q: Bisakah kamu menyelesaikan Network Delay Time tanpa heap?

Ya. Dijkstra dengan array biasa memindai setiap simpul yang belum ditetapkan untuk mencari waktu terkecil, yang secara keseluruhan membutuhkan biaya O(n²) . Cara ini lebih unggul pada graf padat, saat E mendekati n². Pada graf jarang, seperti graf dengan 3,000 simpul dan 4,000 sisi, versi heap melakukan jauh lebih sedikit pekerjaan.

SedangJalur terpendek Graf Heap

+10

Sebuah jaringan memiliki n simpul yang diberi label dari 1 hingga n. Tautan times[i] = [u, v, w] membawa sinyal dari simpul u ke simpul v dalam waktu w satuan, hanya dalam arah tersebut.

Sebuah sinyal meninggalkan simpul k pada waktu 0 dan merambat melalui setiap tautan yang dapat dilaluinya. Kembalikan waktu saat simpul terakhir menerimanya, atau -1 jika ada simpul yang tidak pernah menerimanya.

Fungsi

networkDelayTime(times: integer-2d-array, n: integer, k: integer) → integer

timesinteger-2d-array: tautan berarah, masing-masing sebagai [u, v, w]
ninteger: jumlah node
kinteger: node yang mengirimkan sinyal
Mengembalikaninteger: waktu saat node terakhir menerima sinyal, atau -1

Batasan

2 ≤ n ≤ 3000
1 ≤ times.length ≤ 4000
times[i].length = 3
1 ≤ u, v ≤ n dan u ≠ v
0 ≤ w ≤ 100
Tidak ada dua tautan yang memiliki u dan v yang sama.
1 ≤ k ≤ n

Contoh

Input: times = [[1, 2, 4], [1, 3, 1], [3, 2, 2], [2, 4, 1]]n = 4k = 1
Output: 4
Penjelasan: Tautan langsung mencapai simpul 2 pada waktu 4, tetapi rute melalui simpul 3 tiba pada waktu 1 + 2 = 3. Simpul 4 menerima sinyal paling akhir, pada waktu 3 + 1 = 4.

Pertanyaan lanjutan

Misalkan sinyal melemah setelah melewati m tautan. Bagaimana cara menemukan waktu node terakhir mendengarnya dalam batas tersebut?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

Setiap node menerima sinyal dalam waktu yang sama dengan panjang rute tercepat dari k, jadi ini adalah pencarian jalur terpendek dari satu sumber yang diikuti dengan nilai maksimum, atau -1 jika sebuah node tidak memiliki rute. Waktu tempuh link tidak pernah negatif, jadi algoritma Dijkstra menetapkan setiap node satu kali. Di bawah ini, E adalah times.length.

Penelusuran mendalam yang mengunjungi kembali setiap kali menemukan rute yang lebih cepat

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Mulai pencarian secara depth-first dari k, sambil membawa waktu yang telah berlalu, lalu catat waktu kedatangan tercepat untuk setiap node. Rute yang mencapai suatu node tidak lebih cepat daripada catatannya akan berhenti, sedangkan rute yang lebih cepat akan memperbarui catatan dan melanjutkan pencarian. Setiap catatan akhirnya menunjukkan waktu tercepat yang sebenarnya, karena rute tercepat akan memperbaruinya pada suatu titik.

Satu node dapat diperbarui berkali-kali. Susun 18 gerbang dalam satu baris, setiap pasang gerbang dihubungkan oleh tautan gratis dan jalan memutar dengan waktu tempuh 65,536, 32,768, dan seterusnya hingga 1. Jika mencoba jalan memutar terlebih dahulu, pencarian mencapai gerbang terakhir pada 131,072 waktu yang berbeda dan menelusuri semua bagian setelahnya setiap kali: pekerjaan yang bertumbuh secara eksponensial terhadap n.

Algoritma

Atur setiap waktu terbaik ke infinity, lalu dorong (k, 0) ke sebuah stack.
Keluarkan (node, t). Lewati jika t < best[node] tidak terpenuhi, lalu atur best[node] = t.
Dorong (next, t + w) untuk setiap tautan dari node yang waktu tibanya lebih baik daripada best[next].
Saat stack kosong, kembalikan -1 jika ada waktu terbaik yang bernilai tak hingga, jika tidak, kembalikan nilai terbesar.

def networkDelayTime(times, n, k):
    graph = [[] for _ in range(n + 1)]
    for u, v, w in times:
        graph[u].append((v, w))
    INF = float("inf")
    best = [INF] * (n + 1)  # the fastest arrival found so far at each node
    stack = [(k, 0)]
    while stack:
        node, t = stack.pop()
        # A route that is not faster than one already found adds nothing.
        if t >= best[node]:
            continue
        best[node] = t
        # Push in reverse so the first listed edge is explored first.
        for nxt, w in reversed(graph[node]):
            if t + w < best[nxt]:
                stack.append((nxt, t + w))
    worst = 0
    for node in range(1, n + 1):
        if best[node] == INF:
            return -1
        worst = max(worst, best[node])
    return worst

Bellman-Ford: relaksasikan setiap sisi hingga n-1 kali

Intuisi

Simpan waktu sementara dist untuk setiap node, dengan nilai 0 untuk k. Relaksasi sisi u → v menurunkan dist[v] menjadi dist[u] + w jika nilainya lebih kecil. Bellman-Ford merelaksasi setiap sisi pada setiap putaran.

Ambil rute tercepat ke sebuah node, misalnya k → a → b → v. Putaran pertama menetapkan nilai final dist[a], putaran kedua menetapkan dist[b], dan putaran ketiga menetapkan dist[v]. Rute tercepat tidak pernah mengulangi node, jadi rute itu memiliki paling banyak n-1 sisi, dan n-1 putaran menetapkan nilai untuk setiap node.

Setiap putaran membutuhkan biaya O(E). Rantai 3.000 node yang dicantumkan dari ujung terjauhnya ke belakang membutuhkan 2.999 putaran untuk memeriksa 4.000 sisi: sekitar 12 juta operasi relaksasi.

Algoritma

Tetapkan dist[k] = 0 dan semua dist lainnya ke tak terhingga.
Ulangi hingga n-1 kali: untuk setiap tautan [u, v, w], jika dist[u] + w < dist[v], tetapkan dist[v] = dist[u] + w.
Berhenti lebih awal setelah satu putaran yang tidak mengubah apa pun.
Kembalikan -1 jika ada dist yang masih tak terhingga, jika tidak, kembalikan nilai terbesar.

def networkDelayTime(times, n, k):
    INF = float("inf")
    dist = [INF] * (n + 1)
    dist[k] = 0
    # A fastest route visits each node at most once, so it has at most n-1 edges,
    # and n-1 passes over every edge are enough to find it.
    for _ in range(n - 1):
        changed = False
        for u, v, w in times:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                changed = True
        if not changed:  # a pass that improves nothing means every time is final
            break
    worst = 0
    for node in range(1, n + 1):
        if dist[node] == INF:
            return -1
        worst = max(worst, dist[node])
    return worst

Algoritma Dijkstra dengan min-heap

Intuisi

Di antara node yang belum ditetapkan, node dengan waktu sementara terkecil sudah menjadi final. Rute lain ke node itu harus meninggalkan node yang sudah ditetapkan melalui node yang belum ditetapkan dengan waktu setidaknya sebesar itu, dan jalur setelahnya hanya menambah waktu karena tidak ada yang negatif. Jadi, tetapkan node itu, relaksasikan jalurnya sekali, lalu ulangi.

Min-heap menemukan waktu terkecil. Saat nilai node membaik, masukkan entri baru dan biarkan entri lama tetap di tempatnya. Entri yang dikeluarkan dengan waktu di atas dist sudah usang, jadi lewati entri itu. Setiap jalur memasukkan paling banyak satu entri, jadi heap menampung paling banyak E + 1 entri dan totalnya adalah O(E log E).

Algoritma

Atur dist[k] = 0, setiap dist lainnya ke tak hingga, lalu masukkan (0, k) ke min-heap.
Keluarkan (t, node) terkecil; jika t > dist[node], lewati karena sudah kedaluwarsa.
Untuk setiap tautan node → next dengan waktu w, jika t + w < dist[next], atur dist[next] = t + w lalu masukkan (t + w, next).
Saat heap kosong, kembalikan -1 jika ada dist yang tak hingga, jika tidak, kembalikan nilai terbesar.

import heapq


def networkDelayTime(times, n, k):
    graph = [[] for _ in range(n + 1)]
    for u, v, w in times:
        graph[u].append((v, w))
    INF = float("inf")
    dist = [INF] * (n + 1)
    dist[k] = 0
    heap = [(0, k)]  # (arrival time, node), smallest time on top
    while heap:
        t, node = heapq.heappop(heap)
        # A stale entry: this node was already reached sooner.
        if t > dist[node]:
            continue
        # t is now final: every other route reaches node later.
        for nxt, w in graph[node]:
            if t + w < dist[nxt]:
                dist[nxt] = t + w
                heapq.heappush(heap, (t + w, nxt))
    worst = 0
    for node in range(1, n + 1):
        if dist[node] == INF:
            return -1
        worst = max(worst, dist[node])
    return worst

Jebakan dan kasus tepi

Menganggap tautan berjalan dua arah. [3, 1, 2] hanya membawa sinyal dari 3 ke 1, jadi node 3 tidak pernah mendengarnya dalam contoh kedua.
Menggunakan pencarian melebar biasa. Algoritma ini menemukan rute dengan tautan paling sedikit: dalam contoh pertama, algoritma ini memberi node 2 waktu 4, bukan 3.
Melupakan -1. Mengambil nilai maksimum tanpa pemeriksaan akan menghasilkan tak terhingga, atau menyembunyikan node yang tidak pernah mendengar sinyal.
Menggunakan int terbesar sebagai tak terhingga. dist[u] + w kemudian meluap menjadi angka negatif untuk u yang belum tercapai; lewati node yang belum tercapai atau gunakan 10^9.

Pertanyaan yang sering diajukan3

Berapa kompleksitas waktu Network Delay Time?

Dengan algoritma Dijkstra dan binary heap, kompleksitas waktunya adalah O(E log E), dengan E sebagai jumlah tautan. Nilai itu sama dengan O(E log n), karena E paling banyak n². Kompleksitas ruangnya adalah O(n + E). Bellman-Ford membutuhkan waktu O(n · E).

Mengapa algoritma Dijkstra membutuhkan bobot yang tidak negatif?

Dijkstra tidak pernah mengunjungi kembali node yang sudah ditetapkan, yang aman hanya jika tidak ada rute berikutnya yang lebih singkat. Dengan jalur A → B berdurasi 2, A → C berdurasi 3, dan C → B berdurasi -2, algoritma ini menetapkan B pada 2, tetapi rute melalui C mencapainya pada 1. Bellman-Ford menangani durasi negatif.

Bisakah kamu menyelesaikan Network Delay Time tanpa heap?

Ya. Dijkstra dengan array biasa memindai setiap simpul yang belum ditetapkan untuk mencari waktu terkecil, yang secara keseluruhan membutuhkan biaya O(n²). Cara ini lebih unggul pada graf padat, saat E mendekati n². Pada graf jarang, seperti graf dengan 3,000 simpul dan 4,000 sisi, versi heap melakukan jauh lebih sedikit pekerjaan.

def networkDelayTime(times, n, k):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

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

Output yang diharapkan

Network Delay Time

Fungsi

Batasan

Contoh

Petunjuk

Solusi

Penelusuran mendalam yang mengunjungi kembali setiap kali menemukan rute yang lebih cepat

Bellman-Ford: relaksasikan setiap sisi hingga n-1 kali

Algoritma Dijkstra dengan min-heap

Jebakan dan kasus tepi

Pertanyaan yang sering diajukan3

Soal serupa