Đơn giản hóa quy trình làm việc của bạn: Tìm kiếm miniwebtool.
Thêm
> Máy tính Đường đi Ngắn nhất Dijkstra
 

Máy tính Đường đi Ngắn nhất Dijkstra

Tìm đường đi ngắn nhất giữa các nút trong đồ thị có trọng số bằng thuật toán Dijkstra. Tính năng bao gồm minh họa đồ thị tương tác, theo dõi hàng đợi ưu tiên từng bước và hiển thị cây đường đi ngắn nhất.

Máy tính Đường đi Ngắn nhất Dijkstra

Thử các đồ thị ví dụ sau:

Mạng lưới đơn giản Mạng lưới lớn Có hướng (CLRS) Lục giác
Định dạng: nguồn, đích, trọng số — mỗi cạnh trên một dòng. Tên nút có thể là chữ cái, số hoặc từ. Tất cả trọng số phải không âm.

Embed Máy tính Đường đi Ngắn nhất Dijkstra Widget

Giới thiệu về Máy tính Đường đi Ngắn nhất Dijkstra

Chào mừng bạn đến với Máy tính đường đi ngắn nhất Dijkstra, một công cụ tương tác để tìm đường đi ngắn nhất trong đồ thị có trọng số bằng thuật toán Dijkstra. Cho dù bạn là sinh viên khoa học máy tính đang học về lý thuyết đồ thị, một chuyên gia mạng đang phân tích các giao thức định tuyến, hay một lập trình viên đang triển khai tìm đường, máy tính này cung cấp sự khám phá trực quan, từng bước về một trong những thuật toán cơ bản nhất trong khoa học máy tính.

Thuật toán Dijkstra là gì?

Thuật toán Dijkstra, được phát minh bởi nhà khoa học máy tính người Hà Lan Edsger W. Dijkstra vào năm 1956, là một thuật toán tìm kiếm đồ thị giải quyết vấn đề đường đi ngắn nhất từ một nguồn duy nhất cho một đồ thị có trọng số với các trọng số cạnh không âm. Cho một nút nguồn, nó tìm đường đi ngắn nhất từ nút đó đến mọi nút khác trong đồ thị.

Thuật toán hoạt động bằng cách duy trì một tập hợp các nút chưa thăm và lặp lại việc chọn nút chưa thăm có khoảng cách tạm thời nhỏ nhất (một chiến lược tham lam). Đây là điều làm cho nó vừa thanh lịch vừa hiệu quả — một khi một nút được "thăm", khoảng cách ngắn nhất của nó được đảm bảo là cuối cùng.

Mã giả thuật toán

function Dijkstra(Graph, source):
  for each node v in Graph:
    dist[v] ← ∞
    prev[v] ← undefined
  dist[source] ← 0
  Q ← priority queue of all nodes

  while Q is not empty:
    u ← node in Q with minimum dist[u]
    remove u from Q

    for each neighbor v of u still in Q:
      alt ← dist[u] + weight(u, v)
      if alt < dist[v]:
        dist[v] ← alt  // nới lỏng
        prev[v] ← u

  return dist[], prev[]

Công thức cốt lõi

Điều kiện nới lỏng cạnh
$$\text{if } d[u] + w(u, v) < d[v] \text{ then } d[v] \leftarrow d[u] + w(u, v)$$

Trong đó:

  • d[u] = khoảng cách ngắn nhất hiện tại đã biết từ nguồn đến nút u
  • w(u, v) = trọng số của cạnh từ u đến v
  • d[v] = khoảng cách ngắn nhất hiện tại đã biết từ nguồn đến nút v

Cách sử dụng máy tính này

  1. Xác định các cạnh của đồ thị: Nhập các cạnh theo định dạng nguồn, đích, trọng số, mỗi cạnh trên một dòng. Mỗi dòng đại diện cho một kết nối giữa hai nút.
  2. Chọn loại đồ thị: Chọn "Vô hướng" cho các cạnh hai chiều (như đường bộ) hoặc "Có hướng" cho các cạnh một chiều (như tuyến đường bay hoặc liên kết web).
  3. Thiết lập nút nguồn: Nhập nút bắt đầu từ đó tất cả các đường đi ngắn nhất sẽ được tính toán.
  4. Tìm đường đi ngắn nhất: Nhấp vào nút để chạy thuật toán Dijkstra. Khám phá trực quan hóa đồ thị tương tác, bảng khoảng cách và theo dõi từng bước.
  5. Xem qua các bước: Sử dụng các nút Tiếp/Trước để xem thuật toán thực thi từng bước một, với đồ thị làm nổi bật các nút và cạnh được cập nhật trong thời gian thực.

Hiểu kết quả

Bảng khoảng cách

Hiển thị khoảng cách ngắn nhất từ nguồn đến mọi nút, cùng với đường đi đầy đủ. Các nút được đánh dấu ∞ là không thể đến được từ nguồn.

Trực quan hóa đồ thị

Canvas tương tác hiển thị đồ thị của bạn với các nút và cạnh được mã hóa màu:

  • Nút màu xanh lam = Nút nguồn
  • Các nút màu xanh lá cây = Đã thăm (khoảng cách đã chốt)
  • Nút màu cam = Hiện đang được xử lý
  • Các nút màu xám = Chưa thăm
  • Các cạnh màu xanh lá cây = Cây đường đi ngắn nhất

Theo dõi từng bước

Hiển thị quá trình thực thi của thuật toán bao gồm các trích xuất hàng đợi ưu tiên, nới lỏng cạnh và cập nhật khoảng cách tại mỗi bước. Điều này cực kỳ hữu ích để học cách thuật toán hoạt động.

Độ phức tạp thời gian

Hiệu quả của thuật toán Dijkstra phụ thuộc vào cấu trúc dữ liệu được sử dụng cho hàng đợi ưu tiên:

Hàng đợi ưu tiênĐộ phức tạp thời gianTốt nhất cho
Binary Heap\( O((V + E) \log V) \)Mục đích chung, đồ thị thưa
Fibonacci Heap\( O(V \log V + E) \)Đồ thị dày đặc (lý thuyết)
Mảng (không dùng heap)\( O(V^2) \)Đồ thị rất dày đặc, V nhỏ

Trong đó V là số đỉnh (nút) và E là số cạnh. Máy tính này sử dụng triển khai binary heap.

Đồ thị có hướng vs. Vô hướng

  • Đồ thị vô hướng: Một cạnh giữa A và B có nghĩa là bạn có thể đi cả A→B và B→A. Ví dụ: mạng lưới đường bộ, mạng lưới tình bạn, mạch điện.
  • Đồ thị có hướng: Một cạnh từ A đến B chỉ cho phép đi A→B, không nhất thiết là B→A. Ví dụ: siêu liên kết web, người theo dõi Twitter, đường bay, dòng chảy của sông.

Hạn chế của thuật toán Dijkstra

  • Không có trọng số âm: Thuật toán Dijkstra đưa ra kết quả sai với trọng số cạnh âm. Sử dụng Bellman-Ford cho đồ thị có trọng số âm (nhưng không có chu trình âm).
  • Nguồn duy nhất: Nó tìm đường đi ngắn nhất từ một nguồn. Đối với đường đi ngắn nhất cho tất cả các cặp, hãy sử dụng Floyd-Warshall hoặc chạy Dijkstra từ mỗi nút.
  • Không có chu trình âm: Chu trình âm làm cho các đường đi ngắn nhất không xác định được (bạn luôn có thể đi vòng quanh chu trình để giảm khoảng cách vô hạn).

Ứng dụng thực tế

Định vị GPS

Các dịch vụ bản đồ sử dụng các biến thể của thuật toán Dijkstra (thường là với kỹ thuật heuristic A*) để tìm tuyến đường nhanh nhất giữa hai địa điểm. Các giao lộ là các nút, và các đoạn đường là các cạnh có trọng số (theo thời gian hoặc khoảng cách).

Định tuyến mạng

Các giao thức định tuyến Internet như OSPF (Open Shortest Path First) và IS-IS sử dụng thuật toán Dijkstra để tính toán đường đi ngắn nhất qua các sơ đồ mạng. Mỗi bộ định tuyến xây dựng một cây đường đi ngắn nhất để xác định việc chuyển tiếp gói tin.

Phân tích mạng xã hội

Tìm đường dẫn kết nối ngắn nhất giữa những người dùng (mức độ tách biệt), tính toán các phép đo mức độ trung tâm và xác định các nút có ảnh hưởng trong mạng.

Phát triển trò chơi

Tìm đường cho NPC trong trò chơi điện tử sử dụng thuật toán Dijkstra hoặc A* (mở rộng Dijkstra với các phương pháp heuristic) để điều hướng bản đồ trò chơi và tìm đường di chuyển tối ưu.

Chuỗi cung ứng & Hậu cần

Tối ưu hóa lộ trình giao hàng, đường dẫn từ kho đến cửa hàng và mạng lưới vận tải đa phương thức nơi các phương thức vận tải khác nhau có chi phí khác nhau.

Câu hỏi thường gặp

Thuật toán Dijkstra là gì?

Thuật toán Dijkstra là một thuật toán tìm kiếm trên đồ thị giúp tìm đường đi ngắn nhất từ một nút nguồn đến tất cả các nút khác trong đồ thị có trọng số với các trọng số cạnh không âm. Nó sử dụng chiến lược tham lam với hàng đợi ưu tiên (min-heap), luôn xử lý nút chưa thăm có khoảng cách nhỏ nhất đã biết. Độ phức tạp thời gian là O((V + E) log V) với binary heap.

Thuật toán Dijkstra có thể xử lý trọng số cạnh âm không?

Không, thuật toán Dijkstra yêu cầu tất cả trọng số cạnh phải không âm. Trọng số âm có thể khiến thuật toán đưa ra kết quả sai vì một khi nút đã được đánh dấu là đã thăm, khoảng cách của nó được coi là cuối cùng. Đối với đồ thị có trọng số âm (nhưng không có chu trình âm), hãy sử dụng thuật toán Bellman-Ford thay thế.

Sự khác biệt giữa đồ thị có hướng và vô hướng là gì?

Trong đồ thị có hướng, các cạnh có hướng — một cạnh từ A đến B không có nghĩa là có cạnh từ B đến A. Trong đồ thị vô hướng, các cạnh hoạt động theo cả hai chiều — nếu có kết nối giữa A và B, bạn có thể đi theo cả hai hướng. Mạng lưới đường bộ thường được mô hình hóa là đồ thị vô hướng, trong khi các liên kết web và tuyến đường bay là có hướng.

Nới lỏng cạnh (edge relaxation) trong thuật toán Dijkstra là gì?

Nới lỏng cạnh là hoạt động cốt lõi trong thuật toán Dijkstra. Khi thăm một nút u, đối với mỗi nút lân cận v, thuật toán kiểm tra xem đường đi qua u (dist[u] + weight(u,v)) có ngắn hơn khoảng cách hiện tại đã biết đến v (dist[v]) hay không. Nếu ngắn hơn, khoảng cách sẽ được cập nhật (nới lỏng) và v được thêm vào hàng đợi ưu tiên với khoảng cách mới.

Cây đường đi ngắn nhất là gì?

Cây đường đi ngắn nhất (SPT) là một đồ thị con có gốc tại nút nguồn chứa các đường đi ngắn nhất từ nguồn đến tất cả các nút có thể đến được. Mỗi nút (ngoại trừ nguồn) có đúng một nút cha — nút tiền nhiệm trên đường đi ngắn nhất của nó. SPT là một sản phẩm phụ của thuật toán Dijkstra và hữu ích cho việc định tuyến và thiết kế mạng.

Các ứng dụng thực tế của thuật toán Dijkstra là gì?

Thuật toán Dijkstra được sử dụng trong hệ thống định vị GPS, giao thức định tuyến mạng (OSPF, IS-IS), phân tích mạng xã hội, tối ưu hóa đường bay, lập kế hoạch đường đi cho robot, tìm đường trong AI trò chơi, hậu cần chuỗi cung ứng và thiết kế mạng viễn thông. Bất kỳ vấn đề nào có thể được mô hình hóa dưới dạng tìm đường đi ngắn nhất hoặc chi phí thấp nhất trong đồ thị đều có lợi từ thuật toán này.

Tài nguyên bổ sung

Tham khảo nội dung, trang hoặc công cụ này như sau:

"Máy tính Đường đi Ngắn nhất Dijkstra" tại https://MiniWebtool.com/vi// từ MiniWebtool, https://MiniWebtool.com/

bởi đội ngũ miniwebtool. Cập nhật: 19 tháng 2, 2026

Bạn cũng có thể thử AI Giải Toán GPT của chúng tôi để giải quyết các vấn đề toán học của bạn thông qua câu hỏi và trả lời bằng ngôn ngữ tự nhiên.

Công cụ nổi bật:

Máy tính tuổiTrình Trích Xuất Ảnh từ VideoCông cụ đổi Pound sang KilogramCông cụ Mã hóa CaesarCông cụ chuyển đổi kg sang lbsMáy tính giảm giá phần trămMáy tính thương và số dưTrình Tạo Mã MorseCông cụ chuyển đổi chữ số La MãĐảo ngược văn bảnMáy tính phân số tối giảnCông cụ chuyển đổi nhị phân sang thập phânTrình tạo số nguyên ngẫu nhiênCông cụ đếm hàngXóa dấu cáchMáy tính thập phân sang phân sốTrình tạo chuỗi ngẫu nhiênCon số may mắn của tôi là gì?Máy tính Phân tích Thừa số Nguyên tốTrình tạo tên ngẫu nhiênMáy tính xác suất xúc xắcCông cụ chia ảnhBộ chuyển đổi FPSmáy-tính-số-mũ-độ-chính-xác-caoCông cụ chuyển đổi cm sang feet và inchCông cụ chuyển đổi kPa sang psiBộ chuyển đổi Feet và Inch sang CmBộ chuyển đổi thập phân sang nhị phânTrình tạo ngày sinh ngẫu nhiênMáy tính căn bậc haiTrình tạo mê cungMáy phát động vật ngẫu nhiênTrình tạo số xổ sốMáy tính So sánh Phân sốSắp xếp sốMáy tính thời gianCông cụ tạo Sự thật hay Thách đốMáy tính nhị phânCông cụ tạo nhóm ngẫu nhiênMáy tính xác suấtMáy tính giai thừaParaphraser AIMáy tính HEXBộ lặp MP3Máy tính Cạnh huyềnTrình Tạo Màu Ngẫu NhiênTrình tạo đồ vật ngẫu nhiênCông cụ chuyển đổi inch sang centimetBộ giải mã Base64Máy tính Ước số chung lớn nhấtMáy tính ngày trong năm - Hôm nay là ngày thứ mấy trong năm📅 Máy tính ngàySắp xếp theo thứ tự bảng chữ cáiBộ Giải Mã Mã MorseCông cụ chuyển đổi phân số thành hỗn sốTrình tạo Hash MD5Bộ chuyển đổi hex sang thập phânBộ Chuyển Đổi Nhị PhânTrình chuyển đổi SRT sang TXTMáy Tính Giờ Làm ViệcTrình trích xuất âm thanhBộ chuyển đổi HEXMáy tính hoán vịMáy tính ModuloMáy tính One Rep Max (1RM)Đây có phải là Số Nguyên Tố?Bộ chuyển đổi Thập phân sang Thập lục phânTrình tạo PIN ngẫu nhiênBộ chuyển đổi Nhị phân sang HexBộ chuyển đổi RGB sang HexChọn tên ngẫu nhiênMáy tính tương hợp tình yêuTrình tạo oẳn tù tìMáy tính độ lệch chuẩn - Độ chính xác caoCông cụ chuyển đổi hệ thập lục phân sang nhị phânCông cụ chuyển đổi thập phân sang bát phântra-cứu-địa-chỉ-macMáy tính Tổngchuyển đổi từ sang số điện thoạiCông cụ chuyển đổi bát phân sang thập phânCông cụ chuyển đổi centimet sang inchMáy tính Cung Mặt trời, Mặt trăng & Cung mọc 🌞🌙✨AI Trình thêm dấu câuBộ chuyển đổi hệ cơ sốBộ chọn màu hình ảnhBộ nén hình ảnhCông cụ chuyển đổi bát phân sang nhị phânTrình nén VideoTung đồng xuĐiều chỉnh tốc độ videoDanh sách các số nguyên tốGhép VideoMáy tính Log Base 10Máy tính LogaritMáy tính số thiên thầnMáy tính trung bìnhBộ Chuyển Đổi Mã Nhị Phân Sang Mã XámCông cụ chuyển đổi pound sang gamMáy tính BitwiseMáy tính Hoán vị lệch (Giai thừa phụ)Trình tạo Số CatalanTrình xác thực dãy bậc đồ thịMáy tính Cây khung nhỏ nhấtMáy tính Đường đi Ngắn nhất DijkstraTrình tạo Ma phươngMáy tính Số Hạnh phúcMáy tính Phỏng đoán CollatzMáy tính Độ congMáy tính Bán kính Hội tụMáy tính Phân tích LU Ma trậnMáy tính Phép chiếu VectorMáy tính Gram-SchmidtMáy tính Phương trình Hình cầuMáy tính khoảng cách từ điểm đến mặt phẳngMáy tính Trực tâm Tam giácMáy tính Trọng tâm Tam giácMáy tính Công thức Dây giàyMáy tính Phân số liên tụcMáy tính Nghịch đảo Nhân theo Mô-đunMáy tính Thuật toán Euclid Mở rộngMáy tính Hàm Phi EulerMáy tính Định lý Số dư Trung QuốcCông cụ tạo Biểu đồ Venn (3 Tập hợp)Máy tính lý thuyết tập hợpCông cụ tạo bảng chân trịCông cụ chuyển đổi cân nặng người sang kiếnMáy tính Calo cho MèoMáy tính tiết kiệm bóng đènMáy tính Chi phí TắmMáy tính chi phí điện đào BitcoinMáy tính Giá trị Giấy vệ sinhTra cứu ID người dùng InstagramMáy tính Quãng đường Bàn phímTrình tạo Bingo từ thông dụngMáy tính Xác suất Ngày nghỉ ốmMáy tính lương thực tế theo giờMáy tính Cà phê vs. Giấc ngủMáy tính thời gian trả lời emailMáy tính FIRE - Tự do Tài chính, Nghỉ hưu sớmMáy tính thời gian lãng phí đi làmBộ đếm Chi phí Cuộc họpMáy tính lương trong nhà vệ sinhTrình tạo KakuroTrình tạo KenKen (Calcudoku)trình-tạo-nonogram-picrossGiải và luyện trò chơi 24Tạo và giải SudokuMáy tính khay phô maiMáy tính đài phun sô cô laMáy tính ABV CocktailMáy tính khẩu phần mì SpaghettiMáy tính thời gian làm lạnh biaMáy tính Taco BarMáy tính BBQMáy tính quá liều CaffeineCông cụ lập kế hoạch tiệc pizzaMáy tính rượu tiệc cướiMáy tính Nhà gạch LegoMáy tính Lấp đầy Phòng Bỏng ngôMáy tính va chạm đồng xu rơiMáy tính rơi xuyên Trái đấtMáy tính bức xạ chuốiMáy tính năng lượng Chuột HamsterMáy tính Tỷ lệ Lỗi Dịch chuyển Tức thờiMáy tính nấu gà bằng năng lượng động năngMáy tính lực nâng bóng bay HeliMáy tính Thời gian Sống sót ZombieTrình Kiểm Tra Kích Thước Thu Thập GooglebotMáy tính tỷ lệ bãi đỗ xeMáy tính Cây thông NoelMáy Tính Ngày Tận Thế Ma Cà RồngMáy tính giá trị PizzaMáy tính Quầy nước chanhTrình tạo tiểu bang Mỹ ngẫu nhiênTrình tạo lý do ngẫu nhiênTrình tạo hoạt động ngẫu nhiênTrình tạo công thức cocktail ngẫu nhiênCông cụ chọn phim ngẫu nhiênTrình tạo tên miền ngẫu nhiênTrình tạo siêu năng lực ngẫu nhiênTrình tạo Haiku ngẫu nhiênTrình tạo lời nhắc viết ngẫu nhiênTrình tạo IMEI Ngẫu nhiênTrình tạo chân dung người dùng ngẫu nhiênTrình tạo địa chỉ giả ngẫu nhiênTrình tạo số cổng ngẫu nhiênTrình tạo NanoID ngẫu nhiênMáy tính tuổi thọ pinMáy tính độ rộng đường mạch PCBMáy tính sụt ápMáy tính định luật OhmMáy tính mã màu điện trởTrình tạo chuyển hướng HtaccessCông cụ tối ưu SVGCông cụ tạo faviconCông cụ tạo biểu thức CrontabTrình định dạng SQLCông cụ chuyển đổi cURL sang JSONBộ giải mã JWTCông cụ chuyển đổi JSON sang YAMLMáy tính Chuyển đổi MenCông cụ chuyển đổi kích thước khuôn bánhMáy tính độ ẩm bột nhàomáy-tính-tỷ-lệ-bánh-mìMáy tính kích thước thêu chữ thậpMáy tính vảiMáy tính sợi lenMáy tính nước muối và độ mặnMáy tính tỷ lệ pha cà phêMáy tính ABV bia thủ côngMáy tính sáp và tinh dầu thơm nếnMáy tính xút làm xà phòng (SAP)Máy tính kích thước in và độ phân giải (DPI/PPI)Máy tính Golden Hour và Blue HourMáy tính độ sâu trường ảnh (DoF)Máy tính khoảng cách trồng câyMáy tính Chuyển đổi Tỷ lệ Mô hìnhMáy tính vật liệu nền bể cáMáy tính thể tích và mật độ cá bểQuay vòng quayĐổ xúc xắcQuả cầu Thần kỳ 8Trình tạo bài tây ngẫu nhiênCông cụ tạo địa chỉ IP ngẫu nhiênTrình tạo thời gian ngẫu nhiênTrình tạo ngày ngẫu nhiênCông cụ tạo tọa độ ngẫu nhiênCông cụ tạo User-Agent ngẫu nhiênTrình tạo thẻ tín dụng ngẫu nhiênTrình tạo JSON ngẫu nhiênTrình tạo quốc gia ngẫu nhiênCông cụ tạo bảng màu ngẫu nhiênCông cụ tạo Emoji ngẫu nhiênCông cụ tạo bữa ăn ngẫu nhiênTrình tạo nhánh giải đấu ngẫu nhiênCông Cụ Tạo Phân Phối GaussMáy tính Giá trị PipMáy tính Lãi kép Hàng ngàyMáy tính Chiến lược MartingaleMáy tính Tiêu chí KellyMáy tính Stop Loss & Take ProfitMáy tính mở rộng Fibonaccimáy-tính-điểm-xoayMáy tính đòn bẩy tiền điện tửBộ chuyển đổi Satoshi sang Đô laMáy Tính Chênh Lệch Giá Tiền Điện TửMáy tính tổn thất tạm thờiMáy Tính Lợi Nhuận Quyền ChọnMáy Tính Biến Động Ngầm ĐịnhMáy tính Greek Quyền chọnMáy tính Định giá Quyền chọn Black-ScholesMáy tính rủi ro phá sảnMáy tính lợi nhuận bán khốngMáy tính Margin CallMáy Tính Kích Thước Vị Thếmáy tính giá trung bình cổ phiếuCông cụ xóa ký tự vô hìnhCông cụ Chuyển đổi Văn bản sang Danh sách SQLCông cụ trích xuất cột văn bảnMáy tính sự khác biệt danh sáchCông cụ tạo văn bản ZalgoCông cụ tạo nghệ thuật ASCIICông cụ tạo văn bản vô hình