Đồ thị không có chu trình âm, tức là không tồn tại chu trình sao cho tổng trọng số các cạnh trong chu trình đó
Độ dài của đường đi là tổng trọng số của các cạnh trên đường đi đó
Xét hai đỉnh bất kì, ta cần tìm đường đi ngắn nhất giữa chúng.
Có nhiều loại bài toán tìm đường đi ngắn nhất:
Giữa một cặp đỉnh
Từ một đỉnh nguồn , tìm đường đi ngắn nhất đến tất cả các đỉnh còn lại
Tìm đường đi ngắn nhất từ các đỉnh đến đỉnh đích
Tìm đường đi ngắn nhất giữa mọi cặp đỉnh của đồ thị
Để xây dựng các thuật toán tìm đường đi ngắn nhất, ta xét tính chất sau, gọi hàm là đường đi ngắn nhất từ đỉnh đến đỉnh . Giả sử ta đã tìm được giá trị , nếu tồn tại đỉnh sao cho , ta cập nhật .
Thuật toán Bellman-Ford
Thuật toán Bellman-Ford có thể được dùng trên đồ thị có hướng với trọng số có thể âm (nhưng không tồn tại chu trình âm). Sau khi kết thúc thuật toán, ta sẽ có được đường đi ngắn nhất từ một đỉnh đến mọi đỉnh còn lại của đồ thị.
Khởi tạo:
là một mảng chứa độ dài đường đi ngắn nhất giữa hai cạnh và . Ban đầu và với mọi đỉnh , do chưa tìm được đường đi nào giữa và
là mảng chứa đỉnh liền trước trong đường đi ngắn nhất giữa và . Ví dụ, nếu đường đi đó là thì . Khởi tạo với mọi đỉnh
Thuật toán Bellman-Ford thực hiện vòng lặp ( là số đỉnh của đồ thị), trong mỗi vòng lặp:
Duyệt toàn bộ cạnh với trọng số
Với mỗi cạnh , nếu :
cập nhật
cập nhật
Thuật toán có thể kết thúc sớm nếu trong toàn bộ quá trình duyệt cạnh, không có cập nhật nào được thực hiện.
Độ phức tạp của thuật toán:
Về thời gian chạy:
Trường hợp tốt nhất
Trường hợp xấu nhất
Về tài nguyên
Thuật toán Dijkstra
Được sử dụng trên đồ thị với trọng số không âm
Sau khi kết thúc thuật toán, ta thu được đường đi ngắn nhất từ đỉnh đến mọi đỉnh còn lại của đồ thị
Khởi tạo:
là mảng chứa độ dài đường đi ngắn nhất giữa và . Đặt , nếu và nếu ngược lại
là mảng chứa đỉnh liền trước trong đường đi ngắn nhất giữa và
Gán nhãn đỉnh là “đã thăm”
Thuật toán Dijkstra lặp cho đến khi tất cả các đỉnh đều được gán nhãn “đã thăm”, trong mỗi vòng lặp, thực hiện thao tác sau:
Trong các đỉnh chưa được gán nhãn, tìm là đỉnh có nhỏ nhất.
Gán nhãn đỉnh là “đã thăm”
Xét các đỉnh kề với , nếu :
cập nhật
cập nhật
Độ phức tạp của thuật toán Dijkstra là , tuy nhiên điều này có thể được cải thiện đối với đồ thị thưa và sử dụng các cấu trúc dữ liệu phù hợp
Đối với đồ thị không có chu trình
Trong một đồ thị không có chu trình, ta luôn có thể đánh số các đỉnh, sao cho mỗi cung chỉ đi từ đỉnh số nhỏ đến đỉnh số lớn hơn.
Một thuật toán đánh số đỉnh có thể được miêu tả như sau:
Tìm các đỉnh có bán bậc vào bằng 0, do đồ thị không có chu trình nên chắc chắn có đỉnh này. Đánh số các đỉnh theo thứ tự tùy ý
Loại bỏ các đỉnh vừa đánh số và các cạnh kề với nó.
Lặp lại 2 bước trên cho đến khi tất cả các đỉnh đã được đánh số
Độ phức tạp của thuật toán đánh số trên là
Sau khi đã đánh số, ta có thể duyệt các đỉnh theo thứ tự đánh số, thực hiện việc cập nhật tương tự như trên.
Khi này, độ phức tạp của thuật toán tìm đường đi ngắn nhất là , do ta chỉ duyệt các cạnh đúng 1 lần
Thuật toán Floyd-Warshall
Có thể sử dụng trên đồ thị có trọng số có thể âm
Sau khi kết thúc thuật toán, ta thu được đường đi ngắn nhất giữa mọi cặp đỉnh của đồ thị
Giả sử các đỉnh được đánh số từ đến
Khởi tạo
là ma trận lưu đường đi ngắn nhất giữa hai đỉnh và . nếu
lưu đỉnh liền trước trong đường đi ngắn nhất giữa và . nếu
Gọi và là ma trận đường đi ngắn nhất và đỉnh liền trước, sử dụng đỉnh đầu tiên của đồ thị. ,
Thuật toán Floyd-Warshall xây dựng và với từ đến . và là ma trận có được sau bước “khởi tạo”