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.
Image CAPTCHA
Enter the characters shown in the image.

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

 
Thủ thuật tối ưu Video cho website

Thủ thuật tối ưu Video cho website

Để videos của bạn hiển thị thực tiếp trong trang kết quả tìm kiếm (Search Engine Results Page - SERP), bạn phải tối ưu hóa trang Web, videos và nội dung text xung quanh video.

Giới thiệu jQuery và Subtotaling trong Views Calc Tables - Drupal 7

Giới thiệu jQuery và Subtotaling trong Views Calc Tables - Drupal 7

As a follow up to Drupal 6: Using jQuery to pick up where views_calc falls short, I worked on a project this

Ví dụ viết 1 Unit Test

Ví dụ viết 1 Unit Test trong PHP

Và chúng ta sẽ thực hiện các động tác test nó, bằng cách copy các link của YouTube vào, càng nhiều trường hợp các tốt. Ở đây lưu ý, mặc định thì tham số video id (v=) luôn là tham sau đầu tiên trên URL của YouTube,

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

 

Diet con trung