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: 3.7 (20 votes)
Ảnh của Tommy Tran

Tommy 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

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

 
Theo dõi đơn hàng trong Drupal Commerce với Google Analytics

Theo dõi đơn hàng trong Drupal Commerce với Google Analytics

Knowing what your customers are doing before spending money in your Drupal Commerce store can be valuable information for your business.

The investment case for employing a Drupal core contributor

Một số cách để đầu tư, đóng góp cho Drupal 8 core

I asked my team at Acquia to start tracking the impact of the Drupal core contributors on sales. Below, I'll share some data of how Acquia tracked this and why I'm bullish on there being a business case.

Hướng dẫn cài đặt Alexa Rank và Google PageRank lên website

Hướng dẫn cài đặt Alexa Rank và Google PageRank lên website

Alexa rank và Google pagerank là hai chỉ số dùng để đo thứ hạng, chất lượng các trang web. Đây cũng là những gì mà các nhà quảng cáo nhìn vào đầu tiên để quyết định có nên đặt quảng cáo trên website/blog của bạn hay không.

Công ty diệt chuột T&C

 

Diet con trung