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

 
Apple và Google muốn mua bản quyền Ngoại hạng Anh

Apple và Google muốn mua bản quyền Ngoại hạng Anh

Hai đại gia công nghệ được cho là sẽ gia nhập cuộc đua giành bản quyền phát sóng giải bóng đá ngoại hạng Anh vào cuối năm nay.

FPA - Fast Permissions Access for Drupal

Phân quyền với FPA - Fast Permissions Access trong Drupal

As your Drupal site grows, so does your permissions page. Finding the permissions you need to change often requires a lot of clicking and scrolling.

Android, Sony Ericsson Xperia Arc

Sony Ericsson Xperia Arc Review

If you’re looking for a power-packed, stylish Android phone, Sony Ericsson Xperia Arc has it all. It is one of the thinnest smartphones available these days. Not only that, but it’s also among the easiest to handle Android phones out there.

Tomdesgin.vn

 

Drupal Services