Waktu Tunda Jaringan dan Rekonstruksi Jalur
Selesaikan masalah network-delay-time dengan Dijkstra, rekonstruksi jalur terpendek sebenarnya menggunakan peta pendahulu, dan bahas BFS dua arah untuk graf besar
Waktu Tunda Jaringan dan Rekonstruksi Jalur adalah pelajaran Coding Interview Prep gratis di CoddyKit. Ini adalah pelajaran 4 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar Coding Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Masalah Waktu Tunda Jaringan
Waktu Tunda Jaringan (LeetCode 743): diberikan jaringan dengan n simpul dan sisi berarah berbobot yang menyatakan waktu tempuh sinyal, temukan waktu minimum bagi sinyal yang dikirim dari simpul k untuk mencapai semua simpul. Jika ada simpul yang tidak dapat dijangkau, kembalikan -1. Ini adalah penerapan langsung Dijkstra: jawabannya adalah jarak jalur terpendek maksimum dari k ke semua simpul.
Solusi: Dijkstra + Nilai Maksimum Jarak
Jalankan Dijkstra dari sumber k untuk menemukan dist[v] bagi semua simpul v. Jawabannya adalah max(dist.values()). Jika ada dist[v] yang masih bernilai inf, simpul tersebut tidak dapat dijangkau—kembalikan -1. Sinyal menempuh semua jalur secara bersamaan, sehingga titik pembatasnya adalah simpul yang membutuhkan waktu paling lama untuk dicapai.
import heapq
from collections import defaultdict
def networkDelayTime(times, n, k):
graph = defaultdict(list)
for u, v, w in times:
graph[u].append((v, w))
dist = {i: float('inf') for i in range(1, n+1)}
dist[k] = 0
heap = [(0, k)]
while heap:
d, u = heapq.heappop(heap)
if d > dist[u]:
continue
for v, w in graph[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
heapq.heappush(heap, (dist[v], v))
ans = max(dist.values())
return ans if ans < float('inf') else -1
print(networkDelayTime([[2,1,1],[2,3,1],[3,4,1]], 4, 2)) # 2Rekonstruksi Jalur dengan Larik prev
Untuk merekonstruksi jalur terpendek yang sebenarnya sekaligus menghitung jarak, pertahankan kamus prev yang mencatat pendahulu terbaik untuk setiap simpul. Setiap kali kita memperbarui dist[v], tetapkan prev[v] = u. Setelah Dijkstra selesai, telusuri mundur dari tujuan melalui penunjuk prev hingga mencapai sumber, lalu balik urutannya untuk mendapatkan jalur maju.
import heapq
from collections import defaultdict
def shortest_path_with_reconstruction(times, n, src, dst):
graph = defaultdict(list)
for u, v, w in times:
graph[u].append((v, w))
dist = {i: float('inf') for i in range(1, n+1)}
prev = {i: None for i in range(1, n+1)}
dist[src] = 0
heap = [(0, src)]
while heap:
d, u = heapq.heappop(heap)
if d > dist[u]: continue
for v, w in graph[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
prev[v] = u
heapq.heappush(heap, (dist[v], v))
# Reconstruct path from src to dst
path, node = [], dst
while node is not None:
path.append(node)
node = prev[node]
return dist[dst], path[::-1]BFS Dua Arah untuk Graf Tak Berbobot Berukuran Besar
Untuk graf tak berbobot berukuran besar yang hanya memerlukan satu pasangan sumber-tujuan, BFS dua arah dapat jauh lebih cepat daripada BFS standar. Algoritme ini menjalankan BFS secara bersamaan dari sumber dan tujuan, lalu berhenti saat kedua batas pencarian bertemu. Peningkatan kecepatannya signifikan dalam praktik karena setiap batas pencarian hanya perlu menjelajahi setengah kedalaman graf—mengurangi jumlah simpul yang dijelajahi dari O(b^d) menjadi O(2 × b^(d/2)), dengan b sebagai faktor percabangan.
from collections import deque
def bidir_bfs(graph, src, dst):
if src == dst: return 0
front_q = deque([src]); front_visited = {src: 0}
back_q = deque([dst]); back_visited = {dst: 0}
def expand(queue, visited, other_visited):
node = queue.popleft()
for nxt in graph[node]:
if nxt not in visited:
visited[nxt] = visited[node] + 1
queue.append(nxt)
if nxt in other_visited:
return visited[nxt] + other_visited[nxt]
return -1
while front_q or back_q:
res = expand(front_q, front_visited, back_visited)
if res != -1: return res
res = expand(back_q, back_visited, front_visited)
if res != -1: return res
return -1Kapan Memilih Algoritme yang Tepat
Panduan pengambilan keputusan: Graf tak berbobot, satu pasangan → BFS atau BFS Dua Arah. Berbobot, tidak negatif, satu sumber → Dijkstra. Berbobot, mungkin negatif, satu sumber → Bellman-Ford. Semua pasangan → Floyd-Warshall (V kecil) atau V × Dijkstra (graf jarang). Lompatan terbatas → Bellman-Ford yang dimodifikasi dengan lintasan terbatas. Menyampaikan alasan pengambilan keputusan ini secara lisan dalam wawancara menunjukkan kematangan algoritmik.
Temukan Kota dengan Tetangga yang Dapat Dijangkau Paling Sedikit (LeetCode 1334)
Diberikan kota-kota dengan jalur berbobot dan distanceThreshold, temukan kota yang dapat dijangkau dari paling sedikit kota lain dalam batas tersebut (jika seri, pilih indeks kota yang lebih besar). Solusi: hitung jalur terpendek untuk semua pasangan dengan Floyd-Warshall, lalu hitung untuk setiap kota berapa banyak kota lain yang dapat dijangkau dalam batas tersebut. Kembalikan kota dengan jumlah minimum (jika seri: indeks maksimum).
def findTheCity(n, edges, distanceThreshold):
INF = float('inf')
dist = [[INF]*n for _ in range(n)]
for i in range(n): dist[i][i] = 0
for u, v, w in edges:
dist[u][v] = dist[v][u] = w
for k in range(n):
for i in range(n):
for j in range(n):
dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])
best_city, best_count = -1, n
for city in range(n):
count = sum(1 for j in range(n) if j != city and dist[city][j] <= distanceThreshold)
if count <= best_count:
best_count = count
best_city = city
return best_city
print(findTheCity(4,[[0,1,3],[1,2,1],[1,3,4],[2,3,1]],4)) # 3Jalur dalam DAG Berbobot
Untuk Graf Berarah Tanpa Siklus (DAG), jalur terpendek (atau terpanjang) dapat ditemukan dengan pengurutan topologis + relaksasi dalam O(V+E)—lebih cepat daripada Dijkstra. Proses simpul dalam urutan topologis; saat memproses simpul u, lakukan relaksasi pada semua sisi keluarnya. Untuk jalur terpanjang (berguna dalam penjadwalan proyek atau jalur kritis), ubah tanda bobot atau ubah min menjadi max.
from collections import deque
def dag_shortest_path(V, edges, source):
graph = [[] for _ in range(V)]
in_degree = [0] * V
for u, v, w in edges:
graph[u].append((v, w))
in_degree[v] += 1
# Topological sort (Kahn's)
queue = deque(i for i in range(V) if in_degree[i] == 0)
topo = []
while queue:
node = queue.popleft(); topo.append(node)
for nxt, _ in graph[node]:
in_degree[nxt] -= 1
if in_degree[nxt] == 0: queue.append(nxt)
# Relax in topological order
dist = [float('inf')] * V
dist[source] = 0
for u in topo:
if dist[u] != float('inf'):
for v, w in graph[u]:
dist[v] = min(dist[v], dist[u] + w)
return distJalur Terpendek dalam Matriks dengan Rintangan
Varian wawancara yang umum adalah mencari jalur terpendek dalam kisi 2D dari kiri atas ke kanan bawah, dengan sel-sel yang dapat terhalang. Ini adalah masalah BFS tak berbobot (setiap langkah berbiaya 1). Gunakan BFS dengan pergerakan dalam 4 arah, dan tandai sel sebagai telah dikunjungi saat dimasukkan ke antrean (bukan saat dikeluarkan dari antrean) agar tidak dikunjungi kembali. Jika rintangan dapat dilalui dengan biaya tertentu, gunakan Dijkstra pada kisi 2D dengan memperlakukannya sebagai graf berbobot.
from collections import deque
def shortest_path_binary_matrix(grid):
n = len(grid)
if grid[0][0] == 1 or grid[n-1][n-1] == 1:
return -1
queue = deque([(0, 0, 1)]) # (row, col, distance)
visited = {(0, 0)}
dirs = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]
while queue:
r, c, d = queue.popleft()
if r == n-1 and c == n-1:
return d
for dr, dc in dirs:
nr, nc = r+dr, c+dc
if 0<=nr<n and 0<=nc<n and grid[nr][nc]==0 and (nr,nc) not in visited:
visited.add((nr,nc))
queue.append((nr, nc, d+1))
return -1
print(shortest_path_binary_matrix([[0,0,0],[1,1,0],[1,1,0]])) # 4BFS Multi-Sumber
Saat terdapat beberapa titik awal (misalnya beberapa 'gerbang' dalam kisi atau beberapa titik asal pada peta), jalankan BFS multi-sumber: masukkan semua sumber ke antrean dengan jarak 0 secara bersamaan. Ini menghitung jarak terpendek dari sumber terdekat ke setiap sel dalam satu lintasan BFS. Teknik ini menghindari pelaksanaan BFS secara terpisah dari setiap sumber dan memiliki kompleksitas total O(V+E).
Rangkuman Pemilihan Algoritme
Pohon keputusan singkat: satu sumber, bobot non-negatif → Dijkstra O((V+E) log V). Satu sumber, bobot negatif → Bellman-Ford O(VE). Semua pasangan, V kecil → Floyd-Warshall O(V³). DAG, bobot apa pun → Pengurutan Topologis + Relaksasi O(V+E). Tak berbobot → BFS O(V+E). Jalur pada kisi → BFS (tak berbobot) atau Dijkstra dengan heap (berbobot). Hafalkan tabel ini—tabel tersebut menjawab pertanyaan lanjutan dalam wawancara apa pun tentang jalur terpendek.
Menemukan Jalur dalam Pertanyaan Wawancara
Banyak masalah wawancara meminta jalur yang sebenarnya, bukan hanya biayanya. Selalu pastikan: apakah Anda memerlukan jalurnya atau hanya jaraknya? Jika jalur diperlukan, siapkan kamus prev sejak awal. Kesalahan umum: lupa menginisialisasi prev[source] = None sebagai kondisi terminal, dan keliru dalam urutan rekonstruksi (telusuri kembali dari tujuan ke sumber, lalu balik urutannya). Berlatihlah merekonstruksi jalur pada contoh dengan 3–4 simpul sebelum menerapkannya pada masalah yang lebih besar.
Uji Cepat
Uji pemahaman Anda tentang konsep Struktur Data & Algoritme — Persiapan Wawancara Pemrograman dari pelajaran ini.
Rangkuman Pelajaran
Dalam pelajaran ini Anda mempelajari: Waktu Tunda Jaringan dijawab dengan max(dist.values()) setelah Dijkstra, rekonstruksi jalur menggunakan larik prev yang diperbarui setiap kali dist[v] membaik, dan BFS dua arah dapat mengurangi separuh ruang pencarian untuk jalur terpendek tak berbobot dengan satu pasangan. Selanjutnya, kita mempelajari pengurutan graf dengan Algoritme Kahn untuk pengurutan topologis.
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Waktu Tunda Jaringan dan Rekonstruksi Jalur” gratis?
Ya — teks lengkap “Waktu Tunda Jaringan dan Rekonstruksi Jalur” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Coding Interview Prep, upgrade ke CoddyKit PRO. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Waktu Tunda Jaringan dan Rekonstruksi Jalur”?
Selesaikan masalah network-delay-time dengan Dijkstra, rekonstruksi jalur terpendek sebenarnya menggunakan peta pendahulu, dan bahas BFS dua arah untuk graf besar Kamu berlatih Coding Interview Prep dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.
Apakah aku perlu pengalaman untuk memulai Coding Interview Prep?
Tidak diperlukan pengalaman sebelumnya. Coding Interview Prep di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 4 dari 4.
Berapa lama pelajaran “Waktu Tunda Jaringan dan Rekonstruksi Jalur” memakan waktu?
Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.
Bisakah aku menulis dan menjalankan kode dalam pelajaran Coding Interview Prep ini?
Ya. Setiap pelajaran Coding Interview Prep menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.
Semua pelajaran dalam kursus ini
- Algoritma Dijkstra dengan Antrean Prioritas
- Bellman-Ford dan Siklus Negatif
- Floyd-Warshall: Jalur Terpendek Semua Pasangan
- Waktu Tunda Jaringan dan Rekonstruksi Jalur