Giới thiệu

Chào mừng bạn quay lại với loạt bài Thuật toán đồ thị! Đến giờ, tất cả các cạnh đều có trọng số bằng nhau. Giờ đây, mỗi cạnh có một trọng số (chi phí hoặc khoảng cách), và chúng ta muốn tìm tuyến đường có chi phí thấp nhất.

Thuật toán Dijkstra tìm khoảng cách ngắn nhất từ một đỉnh nguồn đến mọi đỉnh khác trong đồ thị có trọng số cạnh không âm.

Đồ thị có trọng số được biểu diễn bằng n (các đỉnh từ 0 đến n - 1) và edges, một mảng phẳng gồm các bộ ba [u0, v0, w0, u1, v1, w1, ...], trong đó mỗi bộ ba biểu diễn một cạnh có hướng u -> v với trọng số w.

Bắt đầu nào!