Temu Duga Pengekodan: Melaksanakan Algoritma Laluan Terpendek Dijkstra

Prompt dan Skop

Anda diberikan graf berarah dengan n nod yang dilabelkan dari 0 hingga n - 1. Setiap edge ialah tupel (from, to, weight). Diberikan source dan target, kembalikan pasangan yang mengandungi jarak terpendek dan satu laluan terpendek dari source ke target. Kembalikan (-1, []) apabila target tidak dapat dicapai.

Untuk versi ini, anggap 1 <= n <= 100000, 0 <= m <= 300000, setiap label nod adalah sah, dan 0 <= weight <= 10^9. Edge selari, edge berpemberat sifar, dan self-loop adalah dibenarkan. source dan target adalah label yang sah. Jika kedua-duanya sama, kembalikan (0, [source]). Mana-mana laluan terpendek boleh diterima apabila terdapat beberapa laluan dengan jarak yang sama.

Sebagai contoh, dengan edge (0, 1, 4), (0, 2, 1), (2, 1, 2), (1, 3, 1), (2, 3, 5), (3, 4, 3), dan (2, 4, 12), jawapan dari 0 ke 4 ialah jarak 7 dan laluan [0, 2, 1, 3, 4].

Syarat pemberat bukan negatif adalah sebahagian daripada kontrak algoritma. Graf berpemberat tidak dengan sendirinya membayangkan Dijkstra: graf tanpa pemberat memihak kepada BFS, DAG boleh menggunakan pengaturcaraan dinamik topologi, dan graf umum dengan edge negatif memerlukan algoritma seperti Bellman-Ford.

Perkara yang Dinilai oleh Penemu Duga

Isyarat pertama ialah pemilihan algoritma berdasarkan kontrak. Dijkstra sesuai kerana pemberat edge adalah bukan negatif dan hanya satu source yang terlibat. Calon yang mengatakan "graf berpemberat bermaksud Dijkstra" tanpa bertanya tentang pemberat negatif telah terlepas prasyarat yang penting.

Isyarat kedua ialah invariant struktur data. Adjacency matrix memerlukan ruang O(V^2), yang tidak sesuai untuk sehingga 100,000 nod. Adjacency list hanya menyimpan maklumat V + E yang digunakan oleh traversal. Min-heap mendapatkan nod belum selesai (unsettled) dengan jarak ditemui yang terkecil.

Isyarat ketiga ialah cara penurunan jarak diwakili. heapq Python tidak mengemas kini item secara in-place. Penyelesaian praktikal memasukkan (push) pasangan (distance, node) baharu dan kemudian melangkau pasangan lama apabila jaraknya tidak lagi sama dengan distances[node]. Perincian lazy-deletion ini mudah tertinggal dan mengubah kedua-dua penaakulan ketepatan serta batas kekompleksan yang tepat.

Penemu duga juga mengharapkan bukti, bukan sekadar kod yang berfungsi. Jawapan yang mantap menjelaskan sebab entri semasa pertama yang di-pop untuk sesuatu nod adalah muktamad, sebab pemberat bukan negatif menjadikan langkah greedy itu selamat, dan sebab target boleh dikembalikan apabila ia di-pop dan bukannya semasa ia mula-mula ditemui. Pembinaan semula laluan, input tidak boleh dicapai, edge berpemberat sifar, edge selari, lebar integer, dan ujian adversarial melengkapkan jawapan.

Soalan Penjelasan Sebelum Menjawab

• Bolehkah pemberat edge bernilai negatif? Masalah asas menyatakan tidak. Jika edge negatif dibenarkan,

bukti penyelesaian (settling proof) dan early exit Dijkstra tidak lagi sah.

• Adakah graf ini berarah? Ya. Untuk graf tidak berarah, tambahkan kedua-dua arah ke dalam adjacency list.
• Adakah kita hanya memerlukan jarak atau juga laluannya? Versi ini memerlukan kedua-duanya, jadi simpan predecessor

setiap kali pengenduran (relaxation) menambah baik jarak secara ketat.

• Bolehkah terdapat edge selari, edge berpemberat sifar, atau self-loop? Ya. Pengenduran mengendalikannya

tanpa prapemprosesan. Self-loop bukan negatif tidak boleh menambah baik nodnya sendiri.

• Apakah maksud tidak boleh dicapai? Kembalikan (-1, []); jangan kelirukan ia dengan laluan panjang sifar.
• Apabila wujud beberapa laluan terpendek, adakah mana-mana satu boleh diterima? Ya. Pelaksanaan hanya mengemas kini

predecessor pada penambahbaikan ketat, jadi alternatif yang sama tidak mengganggu struktur pepohon laluan.

• Berapa besarkah jarak boleh dicapai? Laluan terpendek mudah mempunyai paling banyak n - 1 edge, jadi di bawah

had yang dinyatakan ia adalah di bawah 10^14. Integer Python tiada had saiz; gunakan integer 64-bit dalam bahasa lebar tetap (fixed-width).

Kerangka Jawapan 30 Saat

"Saya akan membina adjacency list dan menyimpan distances[v], iaitu jarak source-ke-v terbaik yang ditemui setakat ini. Saya mengasalkan source kepada sifar dan meletakkan (0, source) ke dalam min-heap. Setiap kali saya mengeluarkan (pop) entri terkecil, saya melangkauinya jika ia basi (stale). Jika tidak, jarak nod tersebut adalah muktamad kerana setiap edge yang tinggal mempunyai pemberat bukan negatif. Saya mengendurkan setiap edge keluar dan menolak entri heap baharu untuk setiap penambahbaikan ketat, merekodkan predecessor untuk pembinaan semula laluan. Saya boleh berhenti apabila entri semasa target dikeluarkan (pop). Jika jaraknya kekal infiniti, saya kembalikan (-1, []); jika tidak, saya mengikut predecessor ke belakang dan menyongsangkan laluan tersebut. Dengan entri lazy heap, masa ialah O((V + E) log E) dan ruang ialah O(V + E)."

Perbincangan Mendalam Langkah Demi Langkah

Mulakan dengan memisahkan laluan yang ditemui daripada laluan terpendek yang terbukti. distances[v] ialah batas atas bagi jarak terpendek sebenar kerana ia sama ada infiniti atau panjang laluan sebenar yang telah ditemui. Mengendurkan edge u -> v dengan pemberat w menguji sama ada laluan melalui u adalah lebih baik: distances[u] + w < distances[v]. Penambahbaikan ketat mengemas kini kedua-dua jarak dan previous[v].

Heap boleh mengandungi beberapa entri untuk nod yang sama. Dalam contoh, edge 0 -> 1 mula-mula memasukkan jarak 4. Selepas nod 2 diproses, laluan 0 -> 2 -> 1 menambah baik nod 1 kepada jarak 3 dan memasukkan entri kedua. Apabila (4, 1) akhirnya dikeluarkan (pop), 4 != distances[1], jadi ia adalah basi dan mesti diabaikan. Tiada pemadaman item heap secara eksplisit atau set nod dilawati (visited set) diperlukan.

from heapq import heappop, heappush


def shortest_path(
    n: int,
    edges: list[tuple[int, int, int]],
    source: int,
    target: int,
) -> tuple[int, list[int]]:
    graph: list[list[tuple[int, int]]] = [[] for _ in range(n)]
    for node, neighbor, weight in edges:
        if weight < 0:
            raise ValueError("Dijkstra requires non-negative edge weights")
        graph[node].append((neighbor, weight))

    distances = [float("inf")] * n
    previous = [-1] * n
    distances[source] = 0
    heap: list[tuple[int, int]] = [(0, source)]

    while heap:
        distance, node = heappop(heap)
        if distance != distances[node]:
            continue
        if node == target:
            break

        for neighbor, weight in graph[node]:
            candidate = distance + weight
            if candidate < distances[neighbor]:
                distances[neighbor] = candidate
                previous[neighbor] = node
                heappush(heap, (candidate, neighbor))

    if distances[target] == float("inf"):
        return -1, []

    path = []
    node = target
    while node != -1:
        path.append(node)
        node = previous[node]
    path.reverse()
    return int(distances[target]), path

Hujah ketepatan mempunyai dua bahagian. Pertama, setiap nilai terhingga dalam distances ialah panjang laluan sebenar yang ditemui, jadi ia tidak boleh lebih kecil daripada jarak laluan terpendek sebenar. Kedua, andaikan entri semasa untuk u di-pop tetapi wujud laluan yang lebih pendek ke u. Pada laluan tersebut, ambil nod pertama yang belum diselesaikan (unsettled) dan panggil predecessor-nya x. Nod x telah diselesaikan lebih awal, jadi edge keluarnya telah dikendurkan. Oleh itu, nod belum selesai pertama menerima kunci heap yang tidak lebih besar daripada panjang laluan lebih pendek hipotetikal ke u. Oleh kerana semua pemberat edge yang tinggal adalah bukan negatif, kunci tersebut lebih kecil daripada kunci yang di-pop untuk u dan sepatutnya di-pop terlebih dahulu—suatu percanggahan. Oleh itu, jarak semasa yang di-pop adalah muktamad.

Bukti ini juga mentakrifkan titik early-exit yang selamat. Berhenti hanya selepas target di-pop dengan jarak semasa yang bukan basi. Jangan berhenti apabila edge mula-mula menemui target: laluan kemudian mungkin menambah baiknya. Bagi graf contoh, penemuan langsung nod 4 berkos 13, manakala laluan akhir berkos 7.

previous[v] = u merekodkan edge terakhir bagi laluan terbaik semasa ke v. Sebaik sahaja jarak target adalah muktamad, mengikut predecessor pasti akan sampai ke punca kerana setiap penetapan predecessor datang daripada laluan sebenar yang berpunca dari source. Menyongsangkan rantai tersebut mengembalikan laluan dalam susunan ke hadapan. Apabila source sama dengan target, source di-pop serta-merta dan pembinaan semula mengembalikan [source].

Membina adjacency list memerlukan ruang O(V + E) dan masa O(E). Setiap pengenduran yang berjaya menolak satu entri heap, jadi terdapat paling banyak E tolakan sedemikian selain daripada entri awal source. Dengan pendua lazy, heap boleh mengandungi O(E) entri, menghasilkan masa O((V + E) log E) dan jumlah ruang O(V + E). Buku teks sering menyatakan O((V + E) log V) untuk heap yang menyokong decrease-key, atau meringkaskan kepada batas tersebut untuk graf jarang yang mudah. Menyatakan batas log E bagi pelaksanaan lazy adalah lebih tepat.

Uji kontrak, bukan hanya laluan lancar (happy path). Contoh tersebut harus mengembalikan (7, [0, 2, 1, 3, 4]). Edge selari dan pemberat sifar—(0, 1, 10), (0, 1, 2), (1, 2, 0)—harus mengembalikan (2, [0, 1, 2]). Uji juga sasaran yang tidak boleh dicapai, source sama dengan target, self-loop, alternatif sama kos, dan edge berpemberat sifar. Edge negatif harus mencetuskan ralat eksplisit dan bukannya menghasilkan jawapan secara senyap di bawah prasyarat yang rosak.

Ujian pembezaan kecil boleh menjana graf bukan negatif, menjalankan fungsi ini dari setiap source, dan membandingkan jaraknya dengan Bellman-Ford. Bagi laluan yang dikembalikan, sahkan nod pertama dan terakhir, sahkan bahawa setiap pasangan berturutan ialah edge input yang sah, dan jumlahkan pemberat edge yang dipilih. Dengan edge selari, ujian mesti mengaitkan langkah laluan dengan pemberat edge yang sepadan dan bukannya menganggap setiap pasangan nod hanya mempunyai satu edge.

Contoh Jawapan Berkualiti Tinggi

"Saya akan mengesahkan terlebih dahulu bahawa semua pemberat edge adalah bukan negatif, graf adalah berarah, dan mana-mana laluan terpendek boleh diterima. Syarat-syarat tersebut membolehkan saya menggunakan Dijkstra. Saya akan menyimpan edge keluar dalam adjacency list kerana graf boleh mempunyai 100,000 nod dan 300,000 edge; adjacency matrix akan menggunakan memori yang terlalu besar.

distances[v] bermula pada infiniti kecuali untuk source, yang bermula pada sifar. Min-heap menyimpan pasangan (distance, node) yang ditemui. Apabila saya menemui laluan yang lebih pendek melalui nod semasa, saya mengemas kini jarak dan predecessor jiran serta menolak pasangan baharu. Memandangkan heapq tidak mempunyai decrease-key sembarangan, pasangan lama kekal dalam heap. Saya mengesannya dengan membandingkan jarak yang di-pop dengan nilai tatasusunan semasa dan melangkau sebarang ketidakpadanan.

Bukti utama ialah invariant penyelesaian (settling invariant). Apabila entri semasa untuk nod u ialah minimum heap, sebarang laluan hipotetikal yang lebih pendek akan mengandungi nod belum selesai pertama yang predecessor-nya telah diselesaikan. Pengenduran predecessor tersebut sepatutnya telah meletakkan jarak awalan yang sama atau lebih kecil ke dalam heap. Pemberat baki bukan negatif bermakna awalan tersebut sepatutnya di-pop sebelum u, yang merupakan satu percanggahan. Oleh itu u adalah muktamad. Inilah sebabnya saya boleh berhenti apabila entri semasa target di-pop, tetapi bukan apabila target mula-mula dilihat.

Jika target kekal infiniti, saya kembalikan (-1, []). Jika tidak, saya mengikut penunjuk predecessor dari target ke source dan menyongsangkannya. Setiap pengenduran yang berjaya menghasilkan paling banyak satu entri heap baharu, jadi pelaksanaan lazy ini berjalan dalam masa O((V + E) log E) dan menggunakan ruang O(V + E). Dalam bahasa lebar tetap saya akan menggunakan jarak 64-bit. Saya akan menguji entri basi, edge selari dan berpemberat sifar, laluan sama kos, source sama dengan target, input tidak boleh dicapai, dan penolakan edge negatif."

Kesilapan Lazim

• Menjalankan Dijkstra tanpa bertanya tentang pemberat negatif → bukti pemuktamadan greedy terbatal →

Jadikan pemberat bukan negatif sebagai prasyarat eksplisit dan tolak input tidak sah.

• Berhenti apabila sasaran mula-mula dikendurkan → laluan pertama yang ditemui mungkin mahal →

Berhenti hanya apabila entri heap semasa sasaran di-pop.

• Memproses entri heap yang basi → jarak lama mengimbas edge keluar berulang kali → **Langkau apabila

distance != distances[node].**

• Menandakan nod dilawati apabila ia mula-mula ditolak → laluan lebih pendek kemudiannya dihalang → **Sesuatu nod

hanya dianggap selesai (settled) apabila entri minimum semasanya di-pop.**

• Menggunakan adjacency matrix → input jarang (sparse) menggunakan memori O(V^2) → **Gunakan adjacency list dengan

storan O(V + E).**

• Mengemas kini predecessor pada jarak yang sama tanpa peraturan penentu seri → kitaran berpemberat sifar boleh mengubah pilihan

laluan tanpa henti → Gunakan penambahbaikan ketat apabila mana-mana laluan terpendek boleh diterima.

• Mengembalikan jarak terhingga tetapi tiada kontrak laluan → pelaksanaan tidak dapat memenuhi kehendak soalan

→ Rekod predecessor pada setiap penambahbaikan ketat dan bina semula selepas carian.

• Memanggil pelaksanaan heap ini O(E log V) tanpa kelayakan → penduaan lazy boleh menjadikan

saiz heap berkadar dengan E → **Nyatakan O((V + E) log E), kemudian jelaskan batas decrease-key konvensional.**

• Menggunakan jarak 32-bit → laluan boleh melebihi kira-kira 2.1 bilion → **Gunakan integer Python atau jenis

64-bit.**

• Menguji jarak akhir sahaja → rantai predecessor yang salah bentuk tidak disedari → **Sahkan

titik akhir laluan, edge, dan jumlah berat juga.**

Soalan Susulan dan Cara Mengendalikannya

Susulan 1: Apakah yang berubah jika hanya jarak diperlukan?

Keluarkan tatasusunan previous dan pembinaan semula laluan. Carian, bukti, dan batas asimptotik kekal sama, walaupun storan nod tambahan berkurangan sebanyak satu tatasusunan O(V). Early exit semasa pop semasa sasaran kekal selamat.

Susulan 2: Bagaimana jika kita memerlukan jarak terpendek dari setiap punca?

Menjalankan Dijkstra dari setiap nod berkos O(V(V + E) log E) dengan pelaksanaan ini. Untuk graf tumpat, Floyd-Warshall menggunakan masa O(V^3) dan ruang O(V^2) serta turut mengendalikan edge negatif apabila tiada kitaran negatif. Algoritma Johnson menggabungkan pemberatan semula dengan Dijkstra berulang untuk graf jarang dengan edge negatif tetapi tiada kitaran negatif. Buat pilihan berdasarkan ketumpatan graf sebenar dan volum pertanyaan.

Susulan 3: Bagaimana jika edge negatif dibenarkan?

Gunakan Bellman-Ford untuk graf berarah umum. Ia mengendurkan semua edge berulang kali, berjalan dalam O(VE), dan pengenduran berjaya seterusnya mengesan kitaran negatif yang boleh dicapai. Contoh lawan 0 -> 1 = 2, 0 -> 2 = 5, 2 -> 1 = -10 menunjukkan isu tersebut: early-exit Dijkstra menyelesaikan sasaran 1 pada 2, sedangkan laluan sebenar melalui nod 2 berkos -5.

Susulan 4: Bagaimana jika graf ialah DAG dan sesetengah edge adalah negatif?

Lakukan isihan topologi pada DAG, kemudian kendurkan edge keluar sekali mengikut susunan topologi. Setiap predecessor diproses sebelum penggantinya, jadi pemberat negatif adalah selamat dan jumlah masa ialah O(V + E). Ini mengatasi Bellman-Ford dan Dijkstra di bawah kontrak asiklik yang lebih kukuh.

Susulan 5: Bagaimana jika setiap pemberat adalah sama ada 0 atau 1?

Gunakan 0-1 BFS dengan deque. Tolak pengenduran berpemberat sifar ke hadapan (front) dan pengenduran berpemberat satu ke belakang (back). Deque mengekalkan susunan jarak tidak menurun, memberikan masa O(V + E) tanpa heap.

Susulan 6: Bagaimanakah pengemaskinian edge yang kerap akan mengubah reka bentuk?

Untuk pengemaskinian sekali-sekala, bina semula adjacency list atau ubah edge yang terjejas dan jalankan semula Dijkstra; penyelesaian mudah adalah paling mudah untuk disahkan. Pengemaskinian kerap dengan keperluan kependaman yang ketat memerlukan teknik laluan terpendek dinamik atau pepohon sumber bercache dengan pembatalan (invalidation), yang nilainya bergantung pada nisbah kemas kini/pertanyaan dan struktur graf. Jangan mendakwa bahawa perubahan edge setempat hanya menjejaskan dua titik akhirnya.

Susulan 7: Bagaimanakah anda akan mengembalikan laluan terpendek yang terkecil mengikut leksikografi?

Perbandingan jarak yang ketat sahaja tidak mencukupi kerana ia sengaja mengekalkan laluan kos sama yang pertama. Tentukan kontrak susunan terlebih dahulu. Satu pendekatan mengira jarak terpendek, mengehadkan peralihan calon kepada edge yang konsisten dengan jarak tersebut, dan kemudian memilih nod seterusnya yang sah dan paling kecil sambil memastikan sasaran kekal boleh dicapai. Kitaran berpemberat sifar memerlukan pengendalian peka kitaran (cycle-aware). Membandingkan tupel laluan penuh di dalam setiap entri heap adalah lebih mudah untuk input kecil tetapi boleh menambah kos penyalinan dan perbandingan yang ketara.