PricingLoginStart free
Persediaan Temu Duga Pengaturcaraan · Pelajaran

Algoritma Dijkstra dengan Baris Keutamaan

Laksanakan Dijkstra menggunakan heapq, jejaki langkah pelonggaran pada graf berwajaran, dan selesaikan masalah penerbangan termurah dalam k hentian.

Pelajaran 1 daripada 413 langkah

Algoritma Dijkstra dengan Baris Keutamaan ialah pelajaran Persediaan Temu Duga Pengaturcaraan percuma di CoddyKit. Ini ialah pelajaran 1 daripada 4. Anda boleh membaca keseluruhan pelajaran di bawah secara percuma — kemudian berlatih secara praktikal dalam pelayar menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7. Pelajaran ini merupakan sebahagian daripada laluan pembelajaran Persediaan Temu Duga Pengaturcaraan, dan kemajuan anda disegerakkan merentas web serta aplikasi CoddyKit. Kursus Persediaan Temu Duga Pengaturcaraan merangkumi sejumlah 4 pelajaran.

Laluan Terpendek dalam Graf Berwajaran

Algoritma Dijkstra mencari laluan terpendek daripada satu nod sumber kepada semua nod lain dalam graf berwajaran dengan pemberat sisi bukan negatif. Algoritma ini berfungsi dengan memproses nod secara tamak mengikut jarak terbaik yang diketahui pada masa ini — sentiasa mengembangkan nod belum dilawati yang paling hampir. Struktur data utamanya ialah timbunan minimum (baris gilir keutamaan) yang mendapatkan nod dengan jarak paling kecil secara cekap.

Gambaran Keseluruhan Langkah Algoritma

Algoritma Dijkstra: (1) Mulakan dengan dist[source] = 0 dan dist[all others] = inf. (2) Masukkan (0, source) ke dalam timbunan minimum. (3) Keluarkan nod u dengan jarak paling kecil. Jika nod itu sudah dilawati dengan jarak yang lebih kecil, langkaukannya. (4) Bagi setiap jiran v bagi u: jika dist[u] + weight(u,v) < dist[v], kemas kini dist[v] dan masukkan (dist[v], v) ke dalam timbunan. (5) Ulangi sehingga timbunan kosong.

Pelaksanaan Python dengan heapq

Modul Python heapq melaksanakan timbunan minimum. Kita mewakili graf sebagai senarai kejiranan: graph[u] = [(v, weight), ...]. Timbunan menyimpan tupel (distance, node). Kita menggunakan himpunan visited untuk melangkau entri timbunan yang lapuk — entri yang dimasukkan sebelum laluan yang lebih baik ditemui.

import heapq

def dijkstra(graph, source):
    n = len(graph)
    dist = [float('inf')] * n
    dist[source] = 0
    heap = [(0, source)]  # (distance, node)
    visited = set()
    
    while heap:
        d, u = heapq.heappop(heap)
        if u in visited:
            continue
        visited.add(u)
        
        for v, weight in graph[u]:
            if dist[u] + weight < dist[v]:
                dist[v] = dist[u] + weight
                heapq.heappush(heap, (dist[v], v))
    
    return dist

Contoh Berpandu

Pertimbangkan graf dengan 5 nod dan sisi: 0→1 (4), 0→2 (1), 2→1 (2), 1→3 (1), 2→3 (5), 3→4 (3). Laluan terpendek dari nod 0: ke 1 melalui 0→2→1 berkos 3, ke 2 berkos 1, ke 3 melalui 0→2→1→3 berkos 4, dan ke 4 melalui 0→2→1→3→4 berkos 7. Dijkstra menemui semua laluan ini dalam satu laluan pemprosesan, bukan hanya laluan ke satu sasaran.

import heapq

def dijkstra(graph, source):
    dist = [float('inf')] * len(graph)
    dist[source] = 0
    heap = [(0, source)]
    visited = set()
    while heap:
        d, u = heapq.heappop(heap)
        if u in visited:
            continue
        visited.add(u)
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(heap, (dist[v], v))
    return dist

graph = [
    [(1,4),(2,1)],  # 0
    [(3,1)],         # 1
    [(1,2),(3,5)],   # 2
    [(4,3)],         # 3
    []               # 4
]
print(dijkstra(graph, 0))  # [0, 3, 1, 4, 7]

Mengapa Dijkstra Gagal dengan Pemberat Negatif

Ketepatan Dijkstra bergantung pada hakikat bahawa sebaik sahaja nod dikeluarkan daripada timbunan minimum, jaraknya adalah muktamad. Hal ini hanya benar jika pemberat sisi tidak negatif. Dengan sisi negatif u→v yang mempunyai pemberat -5, selepas melawati v, kita mungkin menemukan laluan melalui u yang lebih pendek — tetapi v sudah ditandai sebagai telah dilawati. Satu sisi negatif sahaja boleh menjejaskan semua pengiraan jarak seterusnya.

Penerbangan Termurah dalam K Hentian (LeetCode 787)

Masalah ini menambah satu kekangan: paling banyak k hentian. Dijkstra biasa tidak mengendalikan bilangan langkah secara terbina dalam. Penyelesaian: luaskan keadaan kepada (cost, node, stops_remaining). Gunakan Dijkstra dengan tupel 3 elemen ini, atau gunakan Bellman-Ford dengan k+1 pusingan relaksasi. Dijkstra yang diubah suai berhenti apabila stops_remaining mencapai 0, lalu menghalang lompatan selanjutnya.

import heapq
from collections import defaultdict

def findCheapestPrice(n, flights, src, dst, k):
    graph = defaultdict(list)
    for u, v, w in flights:
        graph[u].append((v, w))
    
    heap = [(0, src, k + 1)]  # (cost, node, hops_left)
    visited = {}  # node -> min hops_left seen at this cost level
    
    while heap:
        cost, node, hops = heapq.heappop(heap)
        if node == dst:
            return cost
        if hops == 0:
            continue
        if visited.get(node, 0) >= hops:
            continue
        visited[node] = hops
        for nxt, w in graph[node]:
            heapq.heappush(heap, (cost + w, nxt, hops - 1))
    return -1

print(findCheapestPrice(4,[[0,1,100],[1,2,100],[0,2,500]],0,2,1))  # 200

Analisis Kerumitan Masa

Dengan timbunan binari, Dijkstra berjalan dalam masa O((V + E) log V): setiap bucu dikeluarkan sekali (V pengeluaran), setiap sisi mungkin mencetuskan satu pemasukan (E pemasukan), dan setiap operasi timbunan memerlukan kos O(log V). Dengan timbunan Fibonacci, batas ini bertambah baik kepada O(E + V log V), tetapi heapq Python ialah timbunan binari. Untuk graf jarang (E ≈ V), versi timbunan binari ialah O(V log V); untuk graf padat (E ≈ V²), versinya ialah O(V² log V).

Membina Semula Laluan Terpendek

Untuk mendapatkan semula laluan sebenar (bukan jarak sahaja), kekalkan tatasusunan prev: apabila mengemas kini dist[v], tetapkan prev[v] = u. Selepas algoritma selesai, bina semula laluan dari sumber ke destinasi dengan menjejakinya ke belakang: mulakan pada dst, ikuti penuding prev sehingga source, kemudian songsangkan hasilnya.

import heapq

def dijkstra_path(graph, source, target):
    n = len(graph)
    dist = [float('inf')] * n
    prev = [-1] * n
    dist[source] = 0
    heap = [(0, source)]
    visited = set()
    while heap:
        d, u = heapq.heappop(heap)
        if u in visited: continue
        visited.add(u)
        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, node = [], target
    while node != -1:
        path.append(node)
        node = prev[node]
    return dist[target], path[::-1]

Menggunakan Kamus untuk Graf Jarang

Apabila nod ialah rentetan atau integer yang tidak berturutan, gunakan defaultdict(list) untuk senarai ketetanggaan dan dict biasa untuk jarak. Perkara ini biasa dalam masalah LeetCode seperti Masa Kelewatan Rangkaian, yang nodnya dilabelkan dari 1 hingga n. Ingatlah untuk menggunakan dist = {node: inf for node in all_nodes} dan periksa nod yang tidak dapat dicapai selepas algoritma selesai.

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))  # 2

Perbandingan dengan BFS untuk Graf Tanpa Pemberat

Untuk graf tanpa pemberat, BFS mencari laluan terpendek dalam O(V + E) — lebih pantas daripada Dijkstra yang mengambil O((V+E) log V). Dijkstra memperluas BFS kepada graf berpemberat dengan menggunakan baris gilir keutamaan dan bukannya baris gilir FIFO biasa. Apabila semua pemberat sisi adalah sama, Dijkstra menjadi BFS. Pilih BFS untuk graf tanpa pemberat, Dijkstra untuk pemberat tidak negatif, dan Bellman-Ford untuk pemberat negatif.

Dijkstra dengan Pengoptimuman Pengurangan Kunci

Dijkstra dalam buku teks menggunakan baris gilir keutamaan dengan pengurangan kunci: apabila jarak sesuatu nod bertambah baik, kemas kini keutamaannya secara terus. Hal ini memerlukan timbunan Fibonacci untuk mendapatkan O(E + V log V), tetapi sukar dilaksanakan. Pendekatan pemadaman malas yang digunakan dalam temu duga pula memasukkan entri baharu dan melangkau pengeluaran entri lapuk — lebih mudah dengan lebihan faktor pemalar sahaja. Dalam Python, pemadaman malas dengan heapq ialah pelaksanaan piawai untuk temu duga.

Semakan Pantas

Uji pemahaman anda tentang konsep Struktur Data & Algoritma — Persediaan Temu Duga Pengekodan daripada pelajaran ini.

Jawab dalam pelajaran interaktif

Imbas Kembali Pelajaran

Dalam pelajaran ini, anda telah mempelajari bahawa: Dijkstra menggunakan timbunan minimum untuk memproses nod secara tamak mengikut jarak terbaik semasa, ia berjalan dalam masa O((V+E) log V) dan gagal pada sisi dengan pemberat negatif, dan entri timbunan lapuk dikendalikan dengan memeriksa set nod yang telah dilawati semasa pengeluaran. Seterusnya, kita membincangkan Bellman-Ford, yang mengendalikan pemberat negatif melalui n-1 pusingan relaksasi.

Percuma untuk bermula

Pelajari Persediaan Temu Duga Pengaturcaraan dengan tutor kecerdasan buatan — percuma

Tulis dan jalankan kod sebenar dalam pelayar anda, dapatkan bantuan segera daripada tutor kecerdasan buatan yang tersedia 24/7, dan sambung semula dari tempat anda berhenti di web atau dalam aplikasi.

Kursus
90
Pelajaran
360
Mula belajar secara percumaLihat kursus penuh

Soalan Lazim

Adakah pelajaran “Algoritma Dijkstra dengan Baris Keutamaan” percuma?

Ya — teks penuh “Algoritma Dijkstra dengan Baris Keutamaan” boleh dibaca secara percuma di web ini. Untuk berlatih secara interaktif menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7, serta membuka kunci baki kursus Persediaan Temu Duga Pengaturcaraan, tingkat taraf kepada CoddyKit PRO. Kursus Persediaan Temu Duga Pengaturcaraan merangkumi sejumlah 4 pelajaran.

Apakah yang akan saya pelajari dalam “Algoritma Dijkstra dengan Baris Keutamaan”?

Laksanakan Dijkstra menggunakan heapq, jejaki langkah pelonggaran pada graf berwajaran, dan selesaikan masalah penerbangan termurah dalam k hentian. Anda berlatih Persediaan Temu Duga Pengaturcaraan menggunakan kod praktikal yang dijalankan terus dalam pelayar, manakala tutor kecerdasan buatan 24/7 menjawab soalan anda semasa anda mengikuti pelajaran.

Adakah saya memerlukan pengalaman untuk memulakan Persediaan Temu Duga Pengaturcaraan?

Tiada pengalaman terdahulu diperlukan. Pembelajaran Persediaan Temu Duga Pengaturcaraan di CoddyKit disusun untuk pelajar daripada peringkat pemula hingga lanjutan, jadi anda boleh bermula di sini atau dari awal dan belajar mengikut kadar anda sendiri. Ini ialah pelajaran 1 daripada 4.

Berapa lamakah pelajaran “Algoritma Dijkstra dengan Baris Keutamaan” diambil?

Kebanyakan pelajaran CoddyKit mengambil masa kira-kira 5–10 minit. Setiap pelajaran ringkas dan interaktif, jadi anda boleh membuat kemajuan secara berterusan dan menyambung tepat dari tempat anda berhenti di web atau aplikasi.

Bolehkah saya menulis dan menjalankan kod dalam pelajaran Persediaan Temu Duga Pengaturcaraan ini?

Ya. Setiap pelajaran Persediaan Temu Duga Pengaturcaraan menyertakan penyunting kod terbina dalam, jadi anda boleh menulis dan menjalankan kod sebenar terus dalam pelayar serta menerima maklum balas kecerdasan buatan serta-merta — tanpa memerlukan persediaan setempat.

Semua pelajaran dalam kursus ini

  1. Algoritma Dijkstra dengan Baris Keutamaan
  2. Bellman-Ford dan Kitaran Negatif
  3. Floyd-Warshall: Laluan Terpendek Semua Pasangan
  4. Masa Kelewatan Rangkaian dan Pembinaan Semula Laluan
← Kembali ke Persediaan Temu Duga Pengaturcaraan