Đường đi ngắn nhất giữa 2 đỉnh trên đồ thị có trọng số cho bởi ma trận trọng số, n cạnh.
Bài này chỉ xét liên thông, nếu xét không liên thông phải thêm điều kiện.

Biến sử dụng:
- Ma trận A (i, j) là ma trận trọng số.
- Đỉnh u (io, jo). Đỉnh v(iv, jv).
- λ(x): Khoảng cách ngắn nhất từ đỉnh u đến đỉnh x.
- S(x): Mảng đánh dấu đỉnh. Nếu x Э S, giá trị S(x) = 1, ngược lại S(x) = 0.

A) Khởi tạo
1) //Đưa tất cả các khoảng cách đỉnh với đỉnh xuất phát u = ∞ và đánh dấu các đỉnh này là 0. Tập lưu trữ các đỉnh này là rỗng, tương ứng với giá trị S(đỉnh) = 0;
FOR i = 1 TO n DO
a) λ(i) = ∞;
b) S(i) = 0;
2) //Đặt khoảng cách cho đỉnh xuất phát là 0, đỉnh xuất phát là u
a) λ(u) = 0;
b) stop := false;

B) Dán nhãn các đỉnh
WHILE (S(v) ≠ 0) & !Stop DO
1)
a) a = v;
b) FOR x := 1 TO n DO
IF (S(x) = 0) & (λ(x) < λ(a)) THEN a := x;
c) IF λ(a) < ∞ THEN S(a) := 1;
ELSE Stop := True;
2) IF Stop = true THEN
FOR (λ(a) < ∞) & (λ(x) > λ(a) + D(a, j)) THEN λ(x) = λ(a) + D(a, x);

C) Chỉ định đường đi
IF !Stop THEN
1) k = j; C(k) = v;
2) WHILE C(k) ≠ u DO
a) x := 1;
WHILE !(D(x, C(k)) < ∞ & λ(C(k) = λ(x) + D(x, C(k))) DO x++;
b) C(k+1) = x; k++;

D)IF (!Stop) THEN Output λ(v), C(k); C(k-1)...C(1);
ELSE Output "Đồ thị không liên thông"

Hình như anh làm nhầm rồi thì phải. Đây là ma trận trọng số chứ có phải là ma trận kề đâu mà anh dùng D(a,i)
Phải viết một function F (x,y: tên đỉnh): giá trị;
- nếu x,y thuộc E thì F:= D(i).t
ELSE F:= +vô cùng;
Khi đó sẽ có điều kiện:
If F(a,i) and lamda(i) = +vô cùng THEN

.........

(xin lỗi vì em lười chèn kí tự nên đành viết tiếng việt :D)

Admin: Bài trên là bài thầy chữa hôm thứ 3 ngày 26/7/2011 tại phòng giao ban Khoa CNTT, lớp mình đi học ở đó. Còn nếu thấy sai thì nên ý kiến với thầy, anh chỉ gõ lại cho những người vắng tham khảo thôi.