ក្បួនដោះស្រាយរបស់ Dijkstra

ក្បួនដោះស្រាយសម្រាប់ស្វែងរកផ្លូវខ្លីបំផុតរវាងថ្នាំងในกราฟ ដែលអាចតំណាងឱ្យឧទាហរណ៍ เครือข่ายถนน។

Visualization

Step 1 / 8

Speed:

Details

Analogy

ลองนึกถึงการค้นหาเส้นทางที่เร็วที่สุดบน GPS อัลกอริทึมจะเริ่มต้นที่ตำแหน่งของคุณ มันจะสำรวจทางแยกที่ใกล้ที่สุดก่อน มันจะติดตาม 'เวลาที่ทราบว่าสั้นที่สุด' เพื่อไปถึงทุกทางแยก เมื่อพบเส้นทางใหม่ที่เร็วกว่าไปยังทางแยกที่ทราบอยู่แล้ว มันจะอัปเดตบันทึกของมัน มันจะกระจายออกไปเรื่อย ๆ โดยให้ความสำคัญกับทางแยกที่ใกล้ที่สุดโดยรวมเสมอ จนกว่าจะพบเส้นทางที่เร็วที่สุดไปยังจุดหมายปลายทางของคุณ

Purpose

เพื่อค้นหาเส้นทางที่สั้นที่สุดจากโหนดต้นทางเดียวไปยังโหนดอื่น ๆ ทั้งหมดในกราฟถ่วงน้ำหนักที่มีน้ำหนักขอบไม่เป็นลบ

Use Cases

โปรโตคอลการกำหนดเส้นทางเครือข่าย, ระบบ GPS สำหรับการค้นหาเส้นทางที่สั้นที่สุด, การวางแผนการบิน และโปรโตคอลการกำหนดเส้นทางแบบ link-state

Algorithm Steps

Line 1

initialize distances[all] = infinity

distances[start] = 0

create priority queue Q

add start to Q

while Q is not empty:

u = vertex with min distance in Q

remove u from Q

for each neighbor v of u:

alt = distances[u] + weight(u, v)

if alt < distances[v]:

distances[v] = alt

add v to Q

Current

Executed

Pending

Explanation

What's Happening?

Step 1/8

ចាប់ផ្តើមที่โหนด A។ ចម្ងាយ: {B: 4, C: 2}។ โหนดที่ใกล้ที่สุดถัดไปคือ C។

Updates with each step • Clickfor full view

Code Implementation

import heapq

def dijkstra(graph, start_node):
    distances = {node: float('infinity') for node in graph}
    distances[start_node] = 0
    priority_queue = [(0, start_node)]
    previous_nodes = {node: None for node in graph}

    while priority_queue:
        current_distance, current_node = heapq.heappop(priority_queue)

        if current_distance > distances[current_node]:
            continue

        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                previous_nodes[neighbor] = current_node
                heapq.heappush(priority_queue, (distance, neighbor))
                
    return distances, previous_nodes