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.7 (15 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: asaleotestf@gmail.com
  • Telegram Messenger: https:/t.me/tommytran0401

Quảng cáo việc làm

 

Thích hợp các bạn nữ mảng thợ may làm việc tại nước NGA

Đơn hàng Tuyển dụng 100 Thợ may đi Nga(đợt 1 tháng 3.2021, đợt 2 tháng 5.2021). Lương thực lãnh 800 USD, bao ăn ở, vé máy bay và visa, phí xuất cảnh(1800 USD)trả khi đi làm có lương. Bạn có thể liên hệ CÔNG TY qua Phone/Zalo: (+84) 944 225 212. Công ty sẽ tư vấn cho bạn.

Xem chi tiết: >>> https://bit.ly/3o9NOfR

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

 
Hướng dẫn alter the Webform submission trước khi lưu database

Hướng dẫn alter the Webform submission trước khi lưu database

In this article we are going to look at a cool Webform api function that allows us to interfere with the submissions being saved to the database.

Hướng dẫn xây dựng SaaS business with Drupal

Hướng dẫn xây dựng SaaS business with Drupal

Have you ever thought about building your own Software-as-a-Service (SaaS) business based on Drupal

Giới thiệu module Organic Groups trong Drupal 6

Giới thiệu module Organic Groups trong Drupal 6

OG allows users to create and manage their own groups. Other members can then join those groups and share content either privately or publicly.