Tìm đường đi ngắn nhất - thuật toán Floyd cài đặt C/C++

Tìm đường đi ngắn nhất - thuật toán Floyd cài đặt C/C++

Xét đồ thị G =<V, E>: trong đó |V| = n, |E| = m. Với mỗi cạnh (u, v)∈E, ta đặt tương ứng với nó một số thực A<u,v> được gọi là trọng số của cạnh. Ta sẽ đặt A[u,v]=∞ nếu (u, v)∉E. Nếu dãy v0, v1,..., vk là một đường đi trên G thì tổng của tất cả các cạnh (A[vi-1,vi]) được gọi là độ dài của đường đi.

Bài toán tìm đường đi ngắn nhất trên đồ thị dưới dạng tổng quát có thể được phát biểu dưới dạng sau: Tìm đường đi ngắn nhất từ một đỉnh xuất phát s∈V(đỉnh nguồn) đến đỉnh cuối t∈V(đỉnh đích). Đường đi như vậy được gọi là đường đi ngắn nhất từ s đến t, độ dài của đường đi d(s,t) được gọi là khoảng cách ngắn nhất từ s đến (trong trường hợp tổng quát d(s,t) có thể âm). Nếu như không tồn tại đường đi từ s đến t thì độ dài đường đi d(s,t)=∞. Nếu như mỗi chu trình trong đồ thị đều có độ dài dương thì trong đường đi ngắn nhất sẽ không có đỉnh nào bị lặp lại, đường đi như vậy được gọi là đường đi cơ bản. Nếu như đồ thị tồn tại một chu trình nào đó có độ dài âm, thì đường đi ngắn nhất có thể không xác định, vì ta có thể đi qua chu trình âm đó một số lần đủ lớn để độ dài của nó nhỏ hơn bất kỳ một số thực cho trước nào.

1. Thuật toán gán nhãn.

Có rất nhiều thuật toán khác nhau được xây dựng để tìm đường đi ngắn nhất. Nhưng tư tưởng chung của các thuật toán đó có thể được mô tả như sau:

Từ ma trận trọng số A[u,v], u,v∈V, ta tìm cận trên d[v] của khoảng cách từ s đến tất cả các đỉnh v∈V. Mỗi khi phát hiện thấy d[u] + A[u,v] < d[v] thì cận trên d[v] sẽ được làm tốt lên bằng cách gán d[v] = d[u] + A[u, v]. Quá trình sẽ kết thúc khi nào ta không thể làm tốt hơn lên được bất kỳ cận trên nào, khi đó d[v] sẽ cho ta giá trị ngắn nhất từ đỉnh s đến đỉnh v. Giá trị d[v] được gọi là nhãn của đỉnh v. Ví dụ dưới đây thể hiện tư tưởng trên bằng một thuật toán gán nhãn tổng quát như sau:

 Ví dụ.Tìm đường đi ngắn nhất từ đỉnh A đến đỉnh I trên đồ thị hình sau:

  • Bước 1.Gán cho nhãn đỉnh A là 0; 
  • Bước 2.Trong số các cạnh (cung) xuất phát từ A, ta chọn cạnh có độ dài nhỏ nhất, sau đó gán nhãn cho đỉnh đó bằng nhãn của đỉnh A cộng với độ dài cạnh tương ứng. Ta chọn được đỉnh C có trọng số AC = 5, nhãn d[C] = 0 + 5 = 5. 
  • Bước 3.Tiếp đó, trong số các cạnh (cung) đi từ một đỉnh có nhãn là A hoặc C tới một đỉnh chưa được gán nhãn, ta chọn cạnh sao cho nhãn của đỉnh cộng với trọng số cạnh tương ứng là nhỏ nhất gán cho nhãn của đỉnh cuối của cạnh. Như vậy, ta lần lượt gán được các nhãn như sau: d[B] = 6 vì d[B] <d[C] + | CB| = 5 + 4; d[E] = 8; Tiếp tục làm như vậy cho tới khi đỉnh I được gán nhãn đó chính là độ dài đường đi ngắn nhất từ A đến I. Thực chất, nhãn của mỗi đỉnh chính là đường đi ngắn nhất từ đỉnh nguồn tới nó. 

Quá trình có thể được mô tả như trong bảng dưới đây.

Bước Đỉnh được gán nhãn Nhãn các đỉnh Đỉnh đã dùng để gán nhãn
Khởi tạo A 0 A
1 C 0+5 =5 A
2 B 0+6 = 6 A
3 E 0+8 = 8 A
4 D 5+4 = 9 C
5 F 5+7 = 13 B
6 H 8+6 = 14 E
7 G 9+6 = 15 D
8 I 15 + 3 = 18 G

Như vậy, độ dài đường đi ngắn nhất từ A đến I là 18. Đường đi ngắn nhất từ A đến I qua các đỉnh: A-> C-> D -> G -> I.

2. Thuật toán Floy

Để tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh của đồ thị, chúng ta có thể sử dụng n lần thuật toán Ford_Bellman hoặc Dijkstra (trong trường hợp trọng số không âm). Tuy nhiên, trong cả hai thuật toán được sử dụng đều có độ phức tạp tính toán lớn (chí ít là O(n^3)). Trong trường hợp tổng quát, người ta thường dùng thuật toán Floy được mô tả như sau:

void Floy(void)

/* Tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh*/

/*Input :  Đồ thị cho bởi ma trận trọng số a[i, j], i, j = 1, 2,..., n.*/

/*Output: - Ma trận đường đi ngắn nhất giữa các cặp đỉnh d[i, j], i, j = 1, 2,...,n;

d[i,j] là độ dài ngắn nhất từ i đến j.

Ma trận ghi nhận đường đi p[i, j], i, j = 1, 2,..., n

p[i, j] ghi nhận đỉnh đi trước đỉnh j trong đường đi ngắn nhất;

*/

{

 /*bước khởi tạo*/

 for (i = 1; i≤n; i++) {

  for (j = 1; j≤n; j++) {

   d[i, j] = a[i, j];

   p[i, j] = i;

  }

 }

 /*bước lặp */

 for (k = 1; k≤n; k++) {

  for (i = 1; i≤n; i++){

   for (j = 1; j≤n; j++) {

    if (d[i, j] > d[i, k] + d[k, j]) {

     d[i, j] = d[i, k] + d[k, j];

     p[i, j] = p[k, j];

    }

   }

  }

 }

}

Chương trình cài đặt thuật toán Folyd tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh của đồ thị được thể hiện như sau:

#include<iostream>

#include<conio.h>

using namespace std;

#define MAX 10000 

#define TRUE 1 

#define FALSE  0 

int A[50][50];// ma trận trọng số của đồ thị.

int D[50][50];//la mang chua cac gia tri khoan cach ngan nhat tu i den j

int S[50][50];//S la mang chua gia tri phan tu ngay sau cua i tren duong di ngan nhat tu i->j */

int n;//số đỉnh của đồ thị

int u;//đỉnh đầu của đường đi

int v;//đỉnh cuối của đường đi

void Init(void){

 freopen("FLOYD.IN", "r", stdin);

 cin>>n>>u>>v;

 cout<<"So dinh cua do thi: "<< n <<endl;

 //nhập ma trận trọng số

 for (int i = 1; i <= n; i++){

  for (int j = 1; j <= n; j++){

   cin>>A[i][j];

   if (i != j && A[i][j] == 0)

    A[i][j] = MAX;

  }

 }

}

void Result(void){

 if (D[u][v] >= MAX) {

  cout<<"Khong co duong di";

 }

 else {

  cout<<"Duong di ngan nhat tu "<<(char)(u+'A'-1)<<" den "<<(char)(v + 'A' -1)<< " co do dai la "<<D[u][v]<<endl;

  cout<<"Duong di: "<<(char)(u + 'A' - 1);//in đỉnh đầu dưới dạng char.

  while (u != v) {

   cout<<"->"<<(char)(S[u][v] +'A' -1);//in ra đường đi dưới dạng char.

   u = S[u][v];

  }

 }

}

void Floy(void){

 int i, j, k, found;

 for (i = 1; i <= n; i++){

  for (j = 1; j <= n; j++){

   D[i][j] = A[i][j];

   if (D[i][j] == MAX) S[i][j] = 0;

   else S[i][j] = j;

  }

 }

 /* Mang D[i,j] la mang chua cac gia tri khoan cach ngan nhat tu i den j

 Mang S la mang chua gia tri phan tu ngay sau cua i tren duong di

 ngan nhat tu i->j */

 for (k = 1; k <= n; k++){

  for (i = 1; i <= n; i++){

   for (j = 1; j <= n; j++){

    if (D[i][k] != MAX && D[i][j] > (D[i][k] + D[k][j])){

     // Tim D[i,j] nho nhat co the co 

     D[i][j] = D[i][k] + D[k][j];

     S[i][j] = S[i][k];

     //ung voi no la gia tri cua phan tu ngay sau i 

    }

   }

  }

 }

}

void main(void){

 Init();

 Floy();

 Result();

 getch();

}

FLOYD.IN input của bài toán

9
1 9
0 6 5 0 8 0 0 0 0
6 0 4 0 0 7 0 0 0
5 4 0 4 0 0 0 0 0
0 0 4 0 4 0 6 0 0
8 0 0 4 0 0 0 6 0
0 7 0 0 0 0 5 0 6
0 0 0 6 0 5 0 4 3
0 0 0 0 6 0 4 0 5
0 0 0 0 0 6 3 5 0
dinh nghia.
1 tuong ung voi dinh A
2 tuong ung voi dinh B
3 tuong ung voi dinh C
4 tuong ung voi dinh D
5 tuong ung voi dinh E
6 tuong ung voi dinh F
7 tuong ung voi dinh G
8 tuong ung voi dinh H
9 tuong ung voi dinh I

Output của chương trình

So dinh cua do thi: 9

Duong di ngan nhat tu A den I co do dai la 18

Duong di: A->C->D->D->I

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

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

 
CasperJS

Hướng dẫn testing Drupal data migrations với CasperJS

On a recent project, the source data is anything but consistent, so while a manual review of one migrated item might look correct, any number of other items could have problems

Dễ dàng thực hiện CSS Regression Testing với Resemble.js trong Drupal 7

Dễ dàng thực hiện CSS Regression Testing với Resemble.js trong Drupal 7

In a nutshell, Resemble.js takes two images, and generates a third that highlights the differences between the source images. Why is that exciting?

Hướng dẫn định dạng dữ liệu tốt hơn trong excel

Hướng dẫn định dạng dữ liệu tốt hơn trong excel

Một trong những việc mà người mới dùng Excel ngại nhất là định dạng dữ liệu, thường người dùng

Wordpress Freelancer

 

Wordpress Freelancer