Trong mạng máy tính, các thuật toán đường đi ngắn nhất nhằm mục đích tìm ra các đường đi tối ưu giữa các nút mạng để chi phí định tuyến được giảm thiểu. Chúng là ứng dụng trực tiếp của các thuật toán đường đi ngắn nhất được đề xuất trong lý thuyết đồ thị.
Giải thích
Coi rằng một mạng bao gồm N đỉnh (nút hoặc thiết bị mạng) được nối với nhau bằng M cạnh (đường truyền). Mỗi cạnh được liên kết với một trọng số, đại diện cho khoảng cách vật lý hoặc độ trễ truyền của đường truyền. Mục tiêu của các thuật toán đường đi ngắn nhất là tìm đường đi giữa bất kỳ cặp đỉnh nào dọc theo các cạnh, do đó tổng trọng số của các cạnh là nhỏ nhất. Nếu các cạnh có trọng số bằng nhau, thuật toán đường đi ngắn nhất nhằm mục đích tìm một tuyến đường có số bước nhảy tối thiểu.
Các thuật toán đường dẫn ngắn nhất phổ biến
Một số thuật toán đường đi ngắn nhất phổ biến là -
-
Thuật toán của Bellman Ford
-
Thuật toán Dijkstra
-
Thuật toán của Floyd Warshall
Các phần sau đây mô tả từng thuật toán này.
Thuật toán Bellman Ford
Đầu vào - Một đồ thị đại diện cho mạng; và một nút nguồn, s
Đầu ra - Đường dẫn ngắn nhất từ s đến tất cả các nút khác.
-
Khởi tạo khoảng cách từ s đến tất cả các nút là vô hạn (∞); khoảng cách đến chính nó bằng 0; một mảng dist [] có kích thước | V | (số nút) với tất cả các giá trị là ∞ ngoại trừ dist [s] .
-
Tính toán quãng đường ngắn nhất theo cách lặp lại. Lặp lại | V | - 1 thời gian cho mỗi nút ngoại trừ s -
-
Lặp lại cho mỗi cạnh nối đỉnh u và v -
-
Nếu dist [v] > (dist [u] + trọng lượng của cạnh u-v) , Sau đó
-
Cập nhật dist [v] =dist [u] + trọng lượng của cạnh u-v
-
-
-
-
Mảng dist [] chứa đường dẫn ngắn nhất từ s đến mọi nút khác.
Thuật toán Dijkstra
Đầu vào - Một đồ thị đại diện cho mạng; và một nút nguồn, s
Đầu ra - Cây đường dẫn ngắn nhất, spt [], với s là nút gốc.
Khởi tạo -
-
Một mảng khoảng cách dist [] có kích thước | V | (số nút), trong đó dist [s] =0 và dist [u] =∞ (vô hạn), trong đó u đại diện cho một nút trong biểu đồ ngoại trừ s.
-
Một mảng, Q , chứa tất cả các nút trong biểu đồ. Khi thuật toán chạy xong, Q sẽ trở nên trống rỗng.
-
Tập hợp trống, S , mà các nút đã truy cập sẽ được thêm vào. Khi thuật toán chạy xong, S sẽ chứa tất cả các nút trong biểu đồ.
-
Lặp lại trong khi Q không trống -
-
Xóa khỏi Q , nút, u có dist [u] nhỏ nhất và cái nào không có trong S . Trong lần chạy đầu tiên, dist [s] bị xóa.
-
Thêm u tới S , đánh dấu bạn là đã ghé thăm.
-
Đối với mỗi nút v tiếp giáp với u , cập nhật dist [v] như -
-
Nếu (dist [u] + trọng số của cạnh u-v) < dist [v] , Sau đó
-
Cập nhật dist [v] =dist [u] + trọng lượng của cạnh u-v
-
-
-
-
Mảng dist [] chứa đường dẫn ngắn nhất từ s đến mọi nút khác.
Thuật toán Floyd Warshall
Đầu vào - Ma trận kề chi phí, adj [] [] , đại diện cho các đường dẫn giữa các nút trong mạng.
Đầu ra - Ma trận chi phí đường dẫn ngắn nhất, chi phí [] [] , hiển thị các đường đi ngắn nhất về mặt chi phí giữa mỗi cặp nút trong biểu đồ.
-
Điền chi phí [] [] như sau:
-
If adj [] [] trống thì chi phí [] [] =∞ (vô hạn)
-
chi phí khác [] [] = adj [] []
-
-
N = | V | , ở đâu V đại diện cho tập hợp các nút trong mạng.
-
Lặp lại từ k =1 đến N -
-
Lặp lại từ i =1 đến N -
-
Lặp lại từ j =1 đến N -
-
Nếu chi phí [i] [k] + chi phí [k] [j] < chi phí [i] [j] , Sau đó
-
Cập nhật chi phí [i] [j] := chi phí [i] [k] + chi phí [k] [j]
-
-
-
-
-
Ma trận chi phí [] [] chứa chi phí ngắn nhất từ mỗi nút, i , đến mọi nút khác, j .