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 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

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.
2 + 0 =
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

 
Người dùng Facebook ở Đức được phép dùng tên giả

Người dùng Facebook ở Đức được phép dùng tên giả

Bất kỳ công ty nào hoạt động tại Đức đều sẽ phải tuân theo bộ luật của đất nước này - ủy ban luật pháp tại Hamburg, Đức phán quyết

Chrome lần đầu 'ngang hàng' với Firefox

Chrome lần đầu 'ngang hàng' với Firefox

Trình duyệt mới xuất hiện 2 năm của Google lần đầu tiên đuổi kịp Firefox và dự kiến với đà tăng trưởng này, nó sẽ trở thành á quân trong tháng 11.

iOS 5.1 Outs New iPhone, iPad, and Apple TV Models

iOS 5.1 Outs New iPhone, iPad, and Apple TV Models

Earlier today, Apple released iOS 5.1 Beta. As usual, hackers got right to work dissecting the software to see if there were any secrets hidden within its source code. Previous code-digging has uncovered features like FaceTime over 3G.

Tomdesgin.vn

 

Drupal Services