Lý thuyết đồ thị - Tìm đường đi ngắn nhất từ 1 đỉnh bất kỳ

Lý thuyết đồ thị - Tìm đường đi ngắn nhất từ 1 đỉnh bất kỳ

Tìm đường đi ngắn nhất

1.     Tìm đường đi bằng thuật toán Ford-Bellman

Yêu cầu đầu vào:

Mảng A[MaxV][ MaxV] là ma trận kề của đồ thị G(V, E), 

Biến V là số đỉnh của đồ thị G

Mảng Truoc[MaxV] được khai báo trước để lưu đường đi từ s đến một đỉnh nào đó. Những khai bnáo này được sử dụng như những biến toàn cục cho chương trình.

Lưu ý, thuật toán có thể áp dụng cho đồ thị có trọng số âm, nhưng chỉ sử dụng được cho đồ thị không có chu trình âm.

Source code thuật toán:

void Ford_Bellman(int *d, int s)

{

            for (int v=0; v<V; v++)

            {

                        d[v] = (A[s][v] != 0)? A[s][v] : 32000;

                        Truoc[v] = s;

            }

            d[s] = 0;

            for (int k=0; k<V-2; k++)

                        for (int v=0; v<V; v++)

                                    for (int u=0; v!=s && u<V; u++)

                                                if (d[v] > d[u]+A[u][v] )

                                                {

                                                            d[v] = d[u] + A[u][v];

                                                            Truoc[v] = u;

                                                }

 

}

2.    Tìm đường đi ngắn nhất bằng thuật toán Dijkstra

Thuật toán Dijkstra chỉ áp dụng cho đồ thị có trọng số không âm. Tu tưởng thuật toán cũng dựa trên ý tưởng so sánh d[v] > d[u]+A[u][v] nhưng tối ưu hơn Ford-Bellmann nhờ giảm số vòng lặp lòng nhau trong quá trình xét các đỉnh.

void Dijkstra(int *d, int s)

{

            int T[MaxV];

            for (int v=0; v<V; v++)

            {

                        d[v] = A[s][v];

                        Truoc[v] = s;

            }

            d[s] = 0;         T[s] = 1;

            while ( 1 )

            {

                        int u = -1;

                        for (int z=0; z<V; z++)

                                    if (T[z] != 1 && (u==-1 || d[u] > d[z]))

                                                u = z;

                        if (u == -1)

                                    break;

                        T[u] = 1;

                        for (int v=0; v<V; v++)

                                    if (T[v]!=1 && d[v]>d[u]+A[u][v])

                                    {

                                                d[v] = d[u]+A[u][v];

                                                Truoc[v] = u;

                                    }

            }

}

3.    Tìm đường đi từ đỉnh s đến đỉnh t.

{ Tìm đường đi dựa vào thông tin được lưu trong mảng Truoc[MaxV]

int InDuongDi_sdTruoc(int Truoc[ ], int s, int t)

{

int STACK[MaxV], topS = 0;

     STACK[topS++] = t;

     while (Truoc[ STACK[topS-1] ] != s)

                 STACK[topS++] = Truoc[ STACK[topS-1] ];

     STACK[topS++] = s;


     cout<<"\nDuong di tu "<<s<<" den "<<t<<" la: ";

     for ( int i=topS-1; i>=0; i-- )

                 cout<<STACK[ i ] +1<<"  ";

}

{ Tìm đường đi dựa vào thông tin trọng số đường đi của các đỉnh được lưu trong mảng d[MaxV], không sử dụng thông tin của mảng trước.

Đặc điểm: Nếu đỉnh u là đỉnh trước của v trên đường đi s đến v thì

d[v] == d[u]+A[u][v]

Dựa vào đặc điểm này để tìm ngược đường đi từ s đến t.

int InDuongDi_ksdTruoc(int d[ ], int s, int t)

{

int STACK[MaxV], topS = 0;

     STACK[topS++] = t;

     int v = t;

     while ( v != s )

{

            int v = STACK[topS-1];

            for (int u = 0; u<V; u++)

                        if (d[v] == d[u]+A[u][v])

                                         break;

if ( u == V)

            break;

STACK[topS++] = u;

                 v = u;

}


     cout<<"\nDuong di tu "<<s<<" den "<<t<<" la: ";

     for ( int i=topS-1; i>=0; i-- )

                 cout<<STACK[ i ] +1<<"  ";

}

4.    Cài đặt hàm main ( )

Để hoàn thiện chương trình, phải sử dụng lại những hàm thao tác trên đồ thị đã được xây dựng trước: DocMTKe(…..), XuatMTKe(…..). Hãy copy chúng vào source code của chương trình.

Định nghĩa hàm main ( ) để tìm đường đi trên đồ thị từ đỉnh s đến đỉnh t của đồ thị.

Source code main ( )

int main(int argc, char* argv[])

{

            DocMTKe("D:\\GRAPH1.TXT", A, V);

            XuatMTKe(A, V);


            int s, t;

            printf("Nhap dinh dau, dinh cuoi cua duong di: "); scanf("%d %d", &s, &t);


            int d[MaxV];

            memset( d, 0, sizeof(d) );


            // Ford_Bellman( d, s );       // Chon 1 trong 2, thuat toan nao cung duoc !

            Dijkstra( d, s ) ;


// InDuongDi_sdTruoc(Truoc, s, t);   // Chon 1 trong 2, ham nao cung duoc!

InDuongDi_ksdTruoc(d, s, t);


            getch();

            return 0;

}
Tags: 
Bạn thấy bài viết này như thế nào?: 
Average: 10 (1 vote)
Ả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

Bình luận (0)

 

Add Comment

Plain text

  • No HTML tags allowed.
  • Các địa chỉ web và email sẽ tự động được chuyển sang dạng liên kết.
  • Tự động ngắt dòng và đoạn văn.
CAPTCHA
This question is for testing whether or not you are a human visitor and to prevent automated spam submissions.
7 + 8 =
Solve this simple math problem and enter the result. E.g. for 1+3, enter 4.

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

 
Google thử nghiệm nhiều tính năng mới cho Gmail

Google thử nghiệm nhiều tính năng mới cho Gmail

Google mới mở rộng công cụ tìm kiếm khi tích hợp thêm các kết quả trong Gmail vào trang kết quả tìm kiếm vào ngày 10/8.

Phần 2: Migrating users từ Drupal 7 sang Drupal 8 site

Phần 2: Migrating users từ Drupal 7 sang Drupal 8 site

The Drupal 8 Migration system is very flexible and can be used to migrate many types of data

Vấn đề cơ bản để viết ứng dụng MapReduce

Vấn đề cơ bản để viết ứng dụng MapReduce

Để viết 1 ứng dụng MapReduce chạy trên Hadoop, điều quan trọng nhất là chuẩn bị 2 hàm số Map và Reduce, tuy nhiên cũng còn nhiều thành phần khác cần phải biết. Để dễ hiểu, có thể tóm tắt đường đi của dữ liệu trong ứng dụng MapReduce như hình sau:

Wordpress Freelancer

 

Wordpress Freelancer