Cài đặt chương trình mô phỏng thuật toán Dijkstra bằng Pascal

Cài đặt chương trình mô phỏng thuật toán Dijkstra bằng Pascal

Về thuật toán Dijkstra có 2 loại

  • Tìm đường đi ngắn nhất từ 1 đỉnh nguồn tới 1 đỉnh đích
  • Tìm đường đi ngắn nhất từ 1 đỉnh nguồn tới các đỉnh còn lại của đồ thị.

– Dùng 1 mảng Len[] – Len[i] là khoảng cách ngắn nhất từ đỉnh a tới đỉnh i.

– Dùng 1 mảng S đánh dấu các đỉnh i đặc biệt (các đỉnh i mà thời điểm hiện tại thì đường đi từ a tới i là ngắn nhất).

– Dùng mảng P[] đánh dấu đường đi. P[j] = i nếu i là đỉnh đi trước j trong đường đi ngắn nhất.

– Đặt lại giá trị vô cùng cho các cặp đỉnh không có đường đi.

– Khởi tạo tất cả các đường đi từ a đên các đỉnh khác bằng vô cùng.

– Khởi tạo đường đi từ a đến chính a = 0.

– Duyệt hết các đỉnh V của đồ thị

  • Tìm đỉnh i chưa nằm trong S mà đường đi từ a tới i là ngắn nhất để đưa vào S. Nếu không tìm được đỉnh nào nghĩa là đã duyệt hết các đỉnh có thể đi mà vẫn chưa thấy đỉnh đích => không thể đi được.
  • Nếu tìm được đỉnh i thì duyệt tất cả các đỉnh j chưa nằm trong S. Nếu Len[i] + G[i][j] < Len[j] (trong đó G[i][j] là khoảng cách từ đỉnh i tới đỉnh j) thì gán Len[j] = Len[i] + G[i][j]; và đánh dấu đường đi P[j] = i.

Lưu ý: Do trong C, mảng bắt đầu từ 0. Do vậy các đỉnh khi tính toán thì sẽ tính từ đỉnh 0 đến đỉnh n-1. Tuy nhiên khi hiển thị ra thì vẫn phải là từ đỉnh 1 đến n và trong file input.inp thì đỉnh đầu và đỉnh cuối cũng sẽ được tính từ 1 đến n. Do đó trong code trước khi tính toán ta cần giảm đỉnh đầu và đỉnh cuối đi 1 đơn vị. Sau khi tính toán xong thì khi xuất kết quả lại cần tăng các đỉnh trong đường đi tìm được lên 1 đơn vị để hiển thị đúng (VD ta muốn tính đường đi từ đỉnh 4 đến đỉnh 8, thì đỉnh 4 tương ứng với vị trí thứ 3 trong mảng, đỉnh 8 ứng với vị trí thứ 7 nên ta cần giảm 4 xuống 3, 8 xuống 7 để tính toán. Khi tìm được đường đi, giả sử là 3 -> 5 -> 4 -> 7 thì phải in ra là 4 -> 6 -> 5 -> 8).

Chúng ta sẽ đi thực hành với đồ thị sau theo 2 code là làm ngay trong main và thực hiện theo các hàm:

Thuật toán Dijkstra

file input.inp: hàng đầu tiên thể hiện có 8 điểm, đi từ điểm 4 đến điểm 8. ma trận 8×8 ở dưới là ma trận kề của đồ thị.

1
2
3
4
5
6
7
8
9
8 4 8
0 3 5 2 0 0 0 0
3 0 1 0 7 0 0 0
5 1 0 4 0 1 0 0
2 0 4 0 0 3 6 0
0 7 0 0 0 2 0 3
0 0 1 3 2 0 4 6
0 0 0 6 0 4 0 5
0 0 0 0 3 6 5 0

Cài đặt bằng Pascal

const INP = 'input.txt';
var
        f : text;
        n, i, j, a, b, sum : integer;
        len, s, p : array[1..1000] of integer;
        G : array[1..100,1..100] of integer;
BEGIN

        {doc du lieu tu tep}
        assign(f, INP);
        reset(f);

        readln(f, n, a, b);
        writeln(n, ' ', a, ' ', b);
        sum :=0;
        for i:=1 to n do
        begin
                for j:=1 to n do
                begin
                        read(f, G[i, j]);
                        sum := sum + G[i, j];
                end;
                readln(f);
        end;

        {dat vo cung cho tat ca cap dinh khong co duong di}
        for i:=1 to n do
                for j:=1 to n do
                        if (i <> j) and (G[i, j] = 0) then
                                G[i, j] := sum;

        for i:=1 to n do
        begin
                len[i] := sum; {khoi tao do dai tu a toi moi dinh la vo cung}
                s[i] := 0;     {danh sach cac diem da xet}
                p[i] := a;     {diem bat dau cua moi dinh la a}
        end;                   {do dai tu a den a la 0}
        len[a] := 0;

        while (s[b] = 0) do     {trong khi dinh b chua duoc duyet}
        begin
                for i:=1 to n do    {tim 1 dinh chua xet ma co the di tu a den no}
                begin
                        if (s[i]=0) and (len[i] < sum) then
                        begin
                                break;
                        end;
                end;
                if i>n then      {khong tim thay dinh nao, dung lai}
                begin
                        break;
                end;

                for j:=1 to n do     {tim dinh ma duong di tu a den no la nho nhat}
                        if (s[j] = 0) and (len[i] > len[j]) then i := j;

                s[i] := 1;            {danh dau da duyet}

                for j:=0 to n do      {tinh lai duong di den cac dinh chua xet}
                        if (s[j] = 0) and (len[i] + G[i, j] < len[j]) then
                        begin
                                len[j] := len[i] + G[i, j];
                                p[j] := i;
                        end;
        end;

        i := b;
        while(i <>a) do
        begin
                write(i, ' <-- ');
                i := p[i];
        end;
        writeln(a);
END.
Bạn thấy bài viết này như thế nào?: 
Average: 2.6 (16 votes)
Ảnh của Tommy Tran

Tommy Tran owner Express Magazine

Drupal Developer having 9+ year experience, implementation and having strong knowledge of technical specifications, workflow development. Ability to perform effectively and efficiently in team and individually. Always enthusiastic and interseted to study new technologies

  • Skype ID: tthanhthuy
  • Phone/Zalo: (+84) 944 225 212
  • WhatsApp: (+84) 944 225 212
  • Line Messenger: (+84) 944 225 212
  • Email: [email protected]
  • Telegram Messenger: https:/t.me/tommytran0401

Advertisement

 

jobsora

Dich vu khu trung tphcm

Dich vu diet chuot tphcm

Dich vu diet con trung

Quảng Cáo Bài Viết

 
Disappointing iPhone: Android Device Set to Gain

Disappointing iPhone: Android Device Set to Gain

Asian smartphone makers have a chance to exploit a rare letdown from pacesetter Apple Inc. after the new iPhone 4S failed to wow fans and investors, leaving Android rivals better placed to grab market share.

Dự đoán xu hướng thiết kế website phát triển mạnh năm 2013

Dự đoán xu hướng thiết kế website phát triển mạnh năm 2013

Qua đây năm 2012 đã dần qua, chúng ta sẽ bắt đầu cho một năm mới và xu hướng thiết kế mới được dự đoán sẽ phát triển mạnh trong năm 2013. Dưới đây chúng tôi sẽ trình bày 6 xu hướng thiết kế web nổi bật của năm 2013.

Nguyễn Thành Nhân - người Việt trẻ thành danh ở Google

Nguyễn Thành Nhân - người Việt trẻ thành danh ở Google

Ở thung lũng công nghệ cao Silicon, Mỹ có nhiều người Việt Nam trẻ tuổi đang làm việc cho tập đoàn công nghệ hàng đầu thế giới - Google. Họ đang thành công với công việc của mình ở xứ người, nhưng vẫn ấp ủ ngày trở về.

Wordpress Freelancer

 

Wordpress Freelancer