0Pricing
DSA Interview Prep · บทเรียน

อัลกอริทึมของ Dijkstra กับคิวลำดับความสำคัญ

นำ Dijkstra ไปใช้งานด้วย heapq ติดตามขั้นตอนการผ่อนคลายบนกราฟถ่วงน้ำหนัก และแก้ปัญหาเที่ยวบินราคาถูกภายในจำนวนจุดแวะไม่เกิน k จุด

อัลกอริทึมของ Dijkstra กับคิวลำดับความสำคัญ เป็นบทเรียน DSA Interview Prep ฟรีบน CoddyKit นี่คือบทเรียนที่ 1 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน DSA Interview Prep และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส DSA Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน

เส้นทางสั้นที่สุดในกราฟถ่วงน้ำหนัก

อัลกอริทึม Dijkstra ใช้ค้นหาเส้นทางสั้นที่สุดจากโหนดต้นทางเพียงโหนดเดียวไปยังโหนดอื่นทั้งหมดใน กราฟถ่วงน้ำหนักที่น้ำหนักของเส้นเชื่อมไม่เป็นลบ อัลกอริทึมนี้ทำงานโดยประมวลผลโหนดตามระยะทางที่ดีที่สุดที่ทราบในปัจจุบัน โดยจะขยายโหนดที่ยังไม่เยี่ยมชมซึ่งอยู่ใกล้ที่สุดเสมอ โครงสร้างข้อมูลสำคัญคือ ฮีปต่ำสุด (คิวลำดับความสำคัญ) ซึ่งดึงโหนดที่มีระยะทางน้อยที่สุดได้อย่างมีประสิทธิภาพ

ภาพรวมขั้นตอนของอัลกอริทึม

อัลกอริทึม Dijkstra: (1) เริ่มต้น dist[source] = 0 และ dist[all others] = inf (2) เพิ่ม (0, source) ลงในฮีปต่ำสุด (3) นำโหนด u ที่มีระยะทางน้อยที่สุดออกมา หากโหนดนี้เคยถูกเยี่ยมชมด้วยระยะทางที่น้อยกว่าแล้ว ให้ข้ามไป (4) สำหรับเพื่อนบ้านแต่ละตัว v ของ u: หาก dist[u] + weight(u,v) < dist[v] ให้อัปเดต dist[v] และเพิ่ม (dist[v], v) ลงในฮีป (5) ทำซ้ำจนกว่าฮีปจะว่าง

การใช้งานในไพธอนด้วยโมดูลคิวฮีป

โมดูล heapq ของไพธอนใช้สร้างฮีปต่ำสุด เราแทนกราฟด้วยรายการเพื่อนบ้าน: graph[u] = [(v, weight), ...] ฮีปเก็บทูเพิล (distance, node) เราใช้เซต visited เพื่อข้ามรายการในฮีปที่เก่าแล้ว ซึ่งเป็นรายการที่ถูกเพิ่มก่อนจะพบเส้นทางที่ดีกว่า

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

ตัวอย่างที่ทำให้ดู

พิจารณากราฟที่มี 5 โหนดและเส้นเชื่อมดังนี้: 0→1 (4), 0→2 (1), 2→1 (2), 1→3 (1), 2→3 (5), 3→4 (3) เส้นทางสั้นที่สุดจากโหนด 0 ได้แก่ ไปยัง 1 ผ่าน 0→2→1 มีค่าใช้จ่าย 3 ไปยัง 2 มีค่าใช้จ่าย 1 ไปยัง 3 ผ่าน 0→2→1→3 มีค่าใช้จ่าย 4 และไปยัง 4 ผ่าน 0→2→1→3→4 มีค่าใช้จ่าย 7 Dijkstra ค้นหาเส้นทางทั้งหมดนี้ได้ในรอบเดียว ไม่ใช่เพียงเส้นทางไปยังเป้าหมายเดียว

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]

เหตุใดอัลกอริทึมไดค์สตราจึงใช้ไม่ได้กับน้ำหนักติดลบ

ความถูกต้องของอัลกอริทึมไดค์สตราอาศัยข้อเท็จจริงที่ว่า เมื่อโหนดถูกนำออกจากมินฮีพแล้ว ระยะทางของโหนดนั้นจะเป็นค่าที่แน่นอน ข้อนี้เป็นจริงเฉพาะเมื่อค่าน้ำหนักของเส้นเชื่อมไม่ติดลบเท่านั้น หากมีเส้นเชื่อมติดลบ u→v ที่มีน้ำหนัก -5 หลังจากเยี่ยมชม v แล้ว เราอาจพบเส้นทางผ่าน u ที่สั้นกว่าได้ แต่ v ถูกทำเครื่องหมายว่าเยี่ยมชมแล้ว เส้นเชื่อมติดลบเพียงเส้นเดียวก็อาจทำให้การคำนวณระยะทางทั้งหมดหลังจากนั้นใช้ไม่ได้

เที่ยวบินราคาถูกที่สุดภายในการหยุดพักไม่เกิน K ครั้ง (LeetCode 787)

ปัญหานี้เพิ่มข้อจำกัดว่า มีจุดแวะพักได้ไม่เกิน k จุด ดิกซ์ตราแบบมาตรฐานไม่รองรับการนับขั้นโดยตรง วิธีแก้คือขยายสถานะเป็น (cost, node, stops_remaining) จากนั้นใช้ดิกซ์ตรากับทูเพิล 3 ค่า หรือใช้ เบลล์แมน–ฟอร์ดกับรอบการผ่อนคลาย k+1 รอบ ดิกซ์ตราที่ปรับแก้จะหยุดเมื่อ stops_remaining มีค่าเป็น 0 เพื่อป้องกันการเดินทางต่อไป

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

การวิเคราะห์ความซับซ้อนด้านเวลา

เมื่อใช้ฮีปแบบไบนารี ดิกซ์ตราจะใช้เวลา O((V + E) log V): แต่ละจุดยอดจะถูกนำออกหนึ่งครั้ง (นำออก V ครั้ง) แต่ละเส้นเชื่อมอาจทำให้เกิดการเพิ่มรายการ (เพิ่ม E ครั้ง) และการดำเนินการกับฮีปแต่ละครั้งมีต้นทุน O(log V) เมื่อใช้ฮีปแบบฟีโบนัชชี ขอบเขตจะดีขึ้นเป็น O(E + V log V) แต่ heapq ของไพธอนเป็นฮีปแบบไบนารี สำหรับกราฟแบบเบาบาง (E ≈ V) รุ่นที่ใช้ฮีปแบบไบนารีมีความซับซ้อน O(V log V) ส่วนกราฟแบบหนาแน่น (E ≈ V²) จะมีความซับซ้อน O(V² log V)

การสร้างเส้นทางสั้นที่สุดขึ้นใหม่

หากต้องการกู้คืนเส้นทางจริง ไม่ใช่เพียงระยะทาง ให้เก็บอาร์เรย์ prev ไว้ เมื่อปรับปรุงค่า dist[v] ให้กำหนด prev[v] = u หลังอัลกอริทึมทำงานเสร็จ ให้สร้างเส้นทางจากต้นทางไปยังปลายทางขึ้นใหม่โดยไล่ย้อนกลับ: เริ่มที่ dst แล้วตามตัวชี้ prev จนถึง source จากนั้นกลับลำดับผลลัพธ์

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]

การใช้ดิกชันนารีกับกราฟแบบเบาบาง

เมื่อโหนดเป็นสตริงหรือจำนวนเต็มที่ไม่เรียงต่อเนื่องกัน ให้ใช้ defaultdict(list) เป็นรายการเพื่อนบ้าน และใช้ dict ปกติเก็บระยะทาง วิธีนี้พบได้บ่อยในโจทย์ LeetCode เช่น โจทย์เวลาในการส่งข้อมูลผ่านเครือข่าย ซึ่งโหนดมีป้ายกำกับตั้งแต่ 1 ถึง n อย่าลืมใช้ dist = {node: inf for node in all_nodes} และตรวจสอบโหนดที่ไม่สามารถเข้าถึงได้หลังอัลกอริทึมทำงานเสร็จ

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

การเปรียบเทียบกับ BFS สำหรับกราฟที่ไม่มีน้ำหนัก

สำหรับกราฟที่ไม่มีน้ำหนัก BFS จะหาเส้นทางสั้นที่สุดได้ในเวลา O(V + E) ซึ่งเร็วกว่าดิกซ์ตราที่ใช้เวลา O((V+E) log V) ดิกซ์ตราขยายแนวคิดของ BFS ไปยังกราฟที่มีน้ำหนัก โดยใช้คิวลำดับความสำคัญแทนคิว FIFO ปกติ เมื่อเส้นเชื่อมทั้งหมดมีน้ำหนักเท่ากัน ดิกซ์ตราจะลดรูปเป็น BFS ให้เลือก BFS สำหรับกราฟที่ไม่มีน้ำหนัก ดิกซ์ตราสำหรับน้ำหนักที่ไม่ติดลบ และเบลล์แมน–ฟอร์ดสำหรับน้ำหนักติดลบ

ดิกซ์ตราพร้อมการปรับปรุงแบบลดคีย์

ดิกซ์ตราตามตำราจะใช้คิวลำดับความสำคัญที่รองรับการลดคีย์: เมื่อระยะทางของโหนดดีขึ้น ให้ปรับลำดับความสำคัญของโหนดนั้นโดยตรง วิธีนี้ต้องใช้ฮีปแบบฟีโบนัชชีเพื่อให้ได้ O(E + V log V) แต่ใช้งานจริงได้ยาก วิธีลบแบบขี้เกียจที่ใช้ในการสัมภาษณ์จะเพิ่มรายการใหม่ แล้วข้ามรายการเก่าที่ถูกนำออกมา จึงเขียนได้ง่ายกว่าโดยมีค่าใช้จ่ายเพิ่มเพียงคงที่ ในไพธอน การลบแบบขี้เกียจร่วมกับ heapq เป็นรูปแบบมาตรฐานที่ใช้ในการสัมภาษณ์

แบบทดสอบสั้น ๆ

ทดสอบความเข้าใจแนวคิดโครงสร้างข้อมูลและอัลกอริทึม — การเตรียมตัวสัมภาษณ์การเขียนโปรแกรมจากบทเรียนนี้

ทบทวนบทเรียน

ในบทเรียนนี้ได้เรียนรู้ว่า: ดิกซ์ตราใช้มินฮีพเพื่อประมวลผลโหนดตามลำดับระยะทางที่ดีที่สุดในปัจจุบันแบบละโมบ อัลกอริทึมใช้เวลา O((V+E) log V) และใช้ไม่ได้กับเส้นเชื่อมที่มีน้ำหนักติดลบ และ รายการเก่าที่ค้างอยู่ในฮีพจะจัดการด้วยการตรวจสอบเซตโหนดที่เยี่ยมชมเมื่อดึงรายการออก บทถัดไปจะกล่าวถึงเบลล์แมน–ฟอร์ด ซึ่งรองรับน้ำหนักติดลบด้วยการผ่อนคลาย V-1 รอบ

คำถามที่พบบ่อย

บทเรียน “อัลกอริทึมของ Dijkstra กับคิวลำดับความสำคัญ” ฟรีหรือไม่

ใช่ — ข้อความเต็มของ “อัลกอริทึมของ Dijkstra กับคิวลำดับความสำคัญ” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส DSA Interview Prep ให้อัปเกรดเป็น CoddyKit PRO คอร์ส DSA Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน

คุณจะเรียนรู้อะไรในบทเรียน “อัลกอริทึมของ Dijkstra กับคิวลำดับความสำคัญ”

นำ Dijkstra ไปใช้งานด้วย heapq ติดตามขั้นตอนการผ่อนคลายบนกราฟถ่วงน้ำหนัก และแก้ปัญหาเที่ยวบินราคาถูกภายในจำนวนจุดแวะไม่เกิน k จุด คุณปฏิบัติ DSA Interview Prep ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน

คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน DSA Interview Prep หรือไม่

ไม่จำเป็นต้องมีประสบการณ์มาก่อน DSA Interview Prep บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 1 จากทั้งหมด 4 บทเรียน

บทเรียน “อัลกอริทึมของ Dijkstra กับคิวลำดับความสำคัญ” ใช้เวลานานแค่ไหน

บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย

ฉันเขียนและรันโค้ดในบทเรียน DSA Interview Prep นี้ได้ไหม

ได้ บทเรียน DSA Interview Prep ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ

บทเรียนทั้งหมดในหลักสูตรนี้

  1. อัลกอริทึมของ Dijkstra กับคิวลำดับความสำคัญ
  2. Bellman-Ford และวงจรน้ำหนักลบ
  3. Floyd-Warshall: เส้นทางสั้นที่สุดระหว่างทุกคู่
  4. เวลาหน่วงของเครือข่ายและการสร้างเส้นทางกลับคืน
← กลับไปที่ DSA Interview Prep