Latihan 1 dari materi Dijkstra — Shortest Path di Algoritma — praktek dengan editor kode interaktif, test case otomatis, dan hint terpandu. Langsung jalan di browser.
Lengkapi dijkstra(graph, start) supaya mengembalikan object berisi jarak terpendek dari start ke tiap kota yang bisa dicapai.
graph berbentuk { kota: [[tetangga, bobot], ...] }. Bobotnya gak ada yang negatif.
start adalah kota awal, jaraknya 0.
Jarak adalah total bobot jalan yang dilewati, bukan jumlah jalannya.
Kota yang gak bisa dicapai dari start jangan dimasukkan ke hasil (jangan diisi Infinity).
Untuk memilih kota terdekat, menyisir semua kota dengan loop sudah cukup, gak perlu min-heap.
Kode di bawah function jangan diubah. Untuk graph di starter, output-nya harus empat baris ini, berurutan:
0 (jarak A)
1 (jarak B)
3 (jarak C, lewat B)
4 (jarak D, lewat B dan C)
Function-nya juga dicek dengan graph lain, termasuk yang punya jalan satu arah.
Hint
Catat jarak sementara tiap kota di object dist, mulai dari start = 0. Ulangi: ambil kota belum selesai yang jaraknya terkecil, lalu cek apakah lewat kota itu ada jalan yang lebih pendek.
Pakai Set done untuk kota yang sudah final. Cari kota terkecil dengan for (const node in dist). Untuk tiap [v, w] di graph[u], hitung dist[u] + w dan ganti dist[v] kalau masih undefined atau lebih besar.
while (true) { let u = null; for (const node in dist) { if (!done.has(node) && (u === null || dist[node] < dist[u])) u = node; } if (u === null) break; done.add(u); for (const [v, w] of graph[u]) { if (dist[v] === undefined || dist[u] + w < dist[v]) dist[v] = dist[u] + w; } }
</>{ }.css=>#idfn()
Versi baru
HyperSheets
bagian dari BelajarWeb.dev
0%
Membuka gerbang…
HyperSheets
Memperbarui Aplikasi
Versi baru tersedia. Halaman akan dimuat ulang otomatis...
