Để tìm đường đi ngắn nhất trong đồ thị bằng Pascal, ta có thể sử dụng thuật toán Dijkstra hoặc thuật toán Bellman-Ford.
Đầu tiên, ta cần tạo một ma trận trọng số để lưu trữ khoảng cách giữa các đỉnh trong đồ thị. Nếu có một cạnh nối giữa hai đỉnh u và v, với trọng số w, ta sẽ lưu trữ giá trị w tại vị trí (u, v) và (v, u) trong ma trận.
Sau đó, ta chọn một đỉnh bất kỳ làm điểm bắt đầu, và tính toán khoảng cách ngắn nhất từ điểm bắt đầu đến các đỉnh khác trong đồ thị bằng thuật toán Dijkstra hoặc Bellman-Ford.
Dưới đây là mã Pascal cho thuật toán Dijkstra:
type
TNode = record
ID: Integer;
Dist: Integer;
end;
var
N: Integer; // số đỉnh trong đồ thị
W: array of array of Integer; // ma trận trọng số
D: array of Integer; // khoảng cách ngắn nhất từ điểm bắt đầu đến các đỉnh khác
Q: array of TNode; // hàng đợi đỉnh cần xử lý
Visited: array of Boolean; // đánh dấu đỉnh đã xét
procedure Dijkstra(S: Integer);
var
i, j, u, v, dist: Integer;
begin
SetLength(D, N);
SetLength(Q, N);
SetLength(Visited, N);
for i := 0 to N - 1 do
begin
D[i] := MaxInt; // khởi tạo khoảng cách ban đầu là vô cực
Visited[i] := False; // đánh dấu chưa xét đỉnh i
end;
D[S] := 0; // khoảng cách từ điểm bắt đầu đến chính nó bằng 0
Q[0].ID := S;
Q[0].Dist := 0;
for i := 1 to N - 1 do
begin
// chọn đỉnh u có khoảng cách ngắn nhất từ điểm bắt đầu đến u
u := -1;
for j := 0 to N - 1 do
if (not Visited[j]) and ((u = -1) or (D[j] < D[u])) then
u := j;
if D[u] = MaxInt then
Break; // không còn đỉnh nào có thể xét được
Visited[u] := True; // đánh dấu đỉnh u đã xét
// cập nhật khoảng cách từ điểm bắt đầu đến các đỉnh kề với u
for v := 0 to N - 1 do
begin
// nếu có cạnh nối giữa u và v
if W[u, v] <> 0 then
begin
dist := D[u] + W[u, v];
if dist < D[v] then
begin
D[v] := dist; // cập nhật khoảng cách ngắn nhất từ điểm bắt đầu đến v
Q[i].ID := v;
Q[i].Dist := dist;
end;
end;
Trong đoạn mã trên, biến S là đỉnh bắt đầu của đường đi ngắn nhất, N là số đỉnh trong đồ thị, W là ma trận trọng số, D là mảng lưu trữ khoảng cách ngắn nhất từ điểm bắt đầu đến các đỉnh khác, Q là hàng đợi đỉnh cần xử lý, Visited là mảng đánh dấu các đỉnh đã xét.
Sau khi chạy hàm Dijkstra với đỉnh bắt đầu là S, ta sẽ có được mảng D chứa khoảng cách ngắn nhất từ điểm bắt đầu đến các đỉnh khác trong đồ thị. Ta có thể in ra kết quả này bằng cách duyệt qua mảng D và in ra các giá trị tương ứng với các đỉnh trong đồ thị.
Chú ý rằng đoạn mã trên chỉ áp dụng cho đồ thị không có cạnh có trọng số âm. Nếu đồ thị có cạnh có trọng số âm, ta cần sử dụng thuật toán Bellman-Ford để tìm đường đi ngắn nhất.
Dưới đây là một ví dụ về cách cài đặt thuật toán Dijkstra bằng ngôn ngữ Pascal:
program ShortestPath;
const
MAXN = 1000;
INF = 1000000000;
type
TEdge = record
v, w: LongInt;
end;
var
S, N, M, u, v, w, i, j, minDist, minNode: LongInt;
W: array[1..MAXN, 1..MAXN] of LongInt; // ma trận trọng số
D: array[1..MAXN] of LongInt; // mảng khoảng cách ngắn nhất
Q: array[1..MAXN] of TEdge; // hàng đợi đỉnh cần xử lý
Visited: array[1..MAXN] of Boolean; // mảng đánh dấu đỉnh đã xét
begin
// Nhập vào số đỉnh N, số cạnh M và đỉnh bắt đầu S
Readln(N, M, S);
// Khởi tạo ma trận trọng số
for i := 1 to N do
for j := 1 to N do
W[i, j] := 0;
// Nhập vào các cạnh và trọng số tương ứng
for i := 1 to M do
begin
Readln(u, v, w);
W[u, v] := w;
end;
// Khởi tạo mảng khoảng cách ngắn nhất và hàng đợi
for i := 1 to N do
begin
D[i] := INF;
Q[i].v := i;
Q[i].w := INF;
end;
// Điểm bắt đầu có khoảng cách ngắn nhất bằng 0
D[S] := 0;
Q[S].w := 0;
// Xử lý hàng đợi cho đến khi nó rỗng
while True do
begin
// Tìm đỉnh có khoảng cách ngắn nhất trong hàng đợi
minDist := INF;
minNode := -1;
for i := 1 to N do
if not Visited[i] and (Q[i].w < minDist) then
begin
minDist := Q[i].w;
minNode := i;
end;
// Nếu không tìm thấy đỉnh có khoảng cách ngắn nhất thì dừng vòng lặp
if minNode = -1 then
Break;
// Đánh dấu đỉnh đã xét
Visited[minNode] := True;
// Xét các đỉnh kề với đỉnh hiện tại và cập nhật khoảng cách ngắn nhất
for i := 1 to N do
begin
if W[minNode, i] <> 0 then
begin
if D[minNode] + W[minNode, i] < D[i] then
begin
D[i] := D[minNode] + W[minNode, i];
Q[i].w := D[i];
end;
end;
end;
// In ra khoảng cách ngắn nhất từ đỉnh bắt đầu đến các đỉnh còn lại
for i := 1 to N do
begin
if D[i] = INF then
Writeln('Khong co duong di tu ', S, ' den ', i)
else
Writeln('Khoang cach ngan nhat tu ', S, ' den ', i, ': ', D[i]);
end;
end.
Đây là một chương trình Pascal cài đặt thuật toán Dijkstra. Chương trình này nhận đầu vào là số đỉnh N
, số cạnh M
và đỉnh bắt đầu S
, sau đó nhập vào danh sách các cạnh và trọng số tương ứng. Cuối cùng, chương trình sử dụng thuật toán Dijkstra để tìm đường đi ngắn nhất từ đỉnh bắt đầu đến các đỉnh còn lại trong đồ thị, và in ra kết quả.