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

Filtered HTML

  • Các địa chỉ web và email sẽ tự động được chuyển sang dạng liên kết.
  • Các thẻ HTML được chấp nhận: <a> <em> <strong> <cite> <blockquote> <code> <ul> <ol> <li> <dl> <dt> <dd>
  • Tự động ngắt dòng và đoạn văn.

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.

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 code entity reference trong custom entities (no bundles)

Entities are a big boon to Drupal, just that the learning curve is a bit longer than CCKs and nodes. I've read a lot about how these entities work but the more I read, the more complex they sound.

“Mổ xẻ” nguyên nhân vấn nạn tin nhắn rác

“Mổ xẻ” nguyên nhân vấn nạn tin nhắn rác sms

Tỉ lệ ăn chia thấp, sức ép từ doanh thu và sự bất cập từ việc quản lí thuê bao di động trả trước… là ngọn nguồn khiến nạn tin nhắn rác, tin nhắn lừa đảo hoạt động “sôi động” như chưa từng có chế tài xử lí.

Kinh doanh internet

Giải pháp kinh doanh trên Internet thời khủng hoảng

Khi khủng hoảng kinh tế ngày một trầm trọng, sức mua của đồng tiền ngày một giảm, việc làm ngày một khan hiếm và tình trạng kinh doanh chưa có dấu hiệu khả quan thì việc đầu tiên mà các công ty

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

 

Diet con trung