[Thuật toán] Tìm đường đi giữa hai đỉnh của đồ thị.

Bài toán: Cho đồ thị G=(V, E). Trong đó V là tập đỉnh, E là tập cạnh của đồ thị. Hãy tìm đường đi từ đỉnh s ∈ Vtới đỉnh t ∈ V.
Thủ tục BFS(s) hoặc DFS(s) cho phép ta duyệt các đỉnh cùng một thành phần liên thông với s. Như vậy, nếu trong số các đỉnh liên thông với s chứa t thì chắc chắn có đường đi từ s đến t. Nếu trong số các đỉnh liên thông với s không chứa t thì không tồn tại đường đi từ s đến t. Do vậy, chúng ta chỉ cần gọi tới thủ tục DFS(s) hoặc BFS(s) và kiểm tra xem đỉnh t có thuộc thành phần liên thông với s hay không. Điều này được thực hiện đơn giản thông qua mảng trạng thái chuaxet[]. Nếu chuaxet[t] =False thì có nghĩa t cùng thành phần liên thông với s. Ngược lại chuaxet[t] = True thì t không cùng thành phần liên thông với s.
Để ghi nhận đường đi từ s đến t, ta sử dụng một mảng truoc[] thiết lập giá trị ban đầu là 0.Trong quá trình duyệt, ta thay thế giá trị của truoc[v] để ghi nhận đỉnh đi trước đỉnh v trong đường đi tìm kiếm từ s đến v. Khi đó, trong thủ tục DFS(v) ta chỉ cần thay đổi lại như sau:

void DFS( int v){ 
 chuaxet[v]:= FALSE; 
 for ( u ∈ke(v) ) { 
  if (chuaxet[u] ) { 
   truoc[u]=v; 
   DFS(u); 
  } 
 } 
}

Đối với thủ tục BFS(v) được thay đổi lại như sau:

void BFS(int u){ 
 queue = φ; 
 u <= queue; /*nạp u vào hàng đợi*/
 chuaxet[u] = false;/* đổi trạng thái của u*/
 while (queue ≠ φ) { /* duyệt tới khi nào hàng đợi rỗng*/
  queue<=p; /*lấy p ra từkhỏi hàng đợi*/
  for (v ∈ke(p) ) {/* đưa các đỉnh v kềvới p nhưng chưa được xét vào hàng đợi*/
   if (chuaxet[v] ) { 
    v<= queue; /*đưa v vào hàng đợi*/
    chuaxet[v] = false;/* đổi trạng thái của v*/
    truoc[v]=p; 
   } 
  } 
 } /* end while*/
}/* end BFS*/

Kết quả đường đi được đọc ngược lại thông qua thủ tục Result() như sau:

void Result(void){ 
 if(truoc[t]==0){ 
  <Không có đường đi từs đến t>; 
  return; 
 } 
 j = t; 
 while(truoc[j]!=s){ 
  <thăm đỉnh j>; 
  j=truoc[j]; 
 } 
 <thăm đỉnh s>; 
} 

Ví dụ. Tìm đường đi từ đỉnh 1 đến đỉnh 7 bằng thuật toán tìm kiếm theo chiều rộng với đồ thị dưới đây:

Tìm đường đi giữa đỉnh 1 đến đỉnh 7 của đồ thị

Ta có, BFS(1) = 1,2,3,11,4,6,12,13,7,8,9,10,5. Rõ ràng chuaxet[7] = True nên có đường đi từ đỉnh 1 đến đỉnh 7. Bây giờ ta xác định giá trị trong mảng truoc[] để có kết quả đường đi đọc theo chiều ngược lại. Truoc[7] = 6; truoc[6] = 2; truoc[2] =1=> đường đi từ đỉnh 1 đến đỉnh 7 là 1 =>2=>6=>7.
Chương trình cài đặt.

#include<iostream>
#include<conio.h>
using namespace std;
#define MAX  100 
#define TRUE  1 
#define FALSE  0
int n;//số đỉnh của đồ thị.
int truoc[MAX], chuaxet[MAX], queue[MAX];//mảng đánh dấu.
int A[MAX][MAX];// ma trận kề của đồ thị.
int s;//đỉnh đầu.
int t;//đỉnh cuối. 

void Init(void){ 
 freopen("lienth.IN", "r",stdin); 
 cin>>n; 
 cout<<"So dinh do thi: "<<n<<endl; 
 cin>>s>>t;
 cout<<"Dinh dau:"<<s<<endl;
 cout<<"Dinh cuoi:"<<t<<endl;
 for(int i=1; i<=n;i++){ 
  for(int j=1; j<=n;j++){ 
   cin>>A[i][j]; 
  }
 } 
 for(int i=1; i<=n;i++){ 
  chuaxet[i]=TRUE; 
  truoc[i]=0; 
 }
 fclose(stdin);
} 
void Result(void){ 
 if(truoc[t]==0){ 
  cout<<"Khong co duong di tu "<<s<< " den "<<t; 
  return; 
 } 
 cout<<"Duong di tu "<<s<<" den "<<t<<" la: "; 
 int j = t;
 cout<<t<<"<="; 
 while(truoc[j]!=s){ 
  cout<<truoc[j]<<"<="; 
  j=truoc[j]; 
 } 
 cout<<s; 
} 
/* Breadth First Search */
void BFS(int s) { 
 int dauQ, cuoiQ, u;
 dauQ=1;cuoiQ=1;//khởi tạo queue.
 queue[dauQ]=s;chuaxet[s]=FALSE; //thêm đỉnh đầu vào queue.
 while (dauQ<=cuoiQ){//queue chưa rỗng.
  u=queue[dauQ];//lấy đỉnh u trong queue.
  dauQ=dauQ+1; 
  for (int p=1; p<=n;p++){ 
   if(A[u][p] && chuaxet[p]){ 
    cuoiQ=cuoiQ+1;
    queue[cuoiQ]=p; 
    chuaxet[p]=FALSE;
    truoc[p]=u; 
   } 
  } 
 } 
} 

void main(void){ 
 Init();
 BFS(s); 
 Result();
 getch(); 
}

Ma trận liền kề được tải về tại đây.
Output của chương trình.

So dinh cua do thi: 13
Dinh dau: 1
Dinh Cuoi: 7
Duong di tu 1 den 7 la: 7<=6<=2<=1

[Bài toán] Tìm đường đi trong ma cung.

[Bài toán] Một mê cung được cho như hình bên dưới. Mê cung là một ma trận có kích thước 100x100. Trong đó màu trắng là đường đi, màu vàng là tường. Hãy tìm đường đi từ điểm bắt đầu có giá trị 2 đến điểm kết thúc có giá trị 3.
 Giả sử đỉnh trên cùng bên trái có tọa độ là (0,0). Điểm bắt đầu là (1,1), điểm kết thúc là (13,13).
Hãy viết chương trình kiểm tra có thể đi từ điểm đầu đến điểm cuối. Nếu có đường đi in ra 1 ngược lại in ra 0.

[Input]
Dữ liệu đầu vào được ghi trong file MAZE.INP.
Dòng đầu ghi số thứ tự test case.
Các dòng tiếp theo là ma trận 100x100.
[Output]
Kết quả ghi ra file MAZE.OUT bắt đầu bằng ký tự #C theo sau là khoảng trắng, 0 nếu không có đường đi, 1 nếu có đường đi.
[I/O example]
Tải file input tại đây..
[Output]
#1 1
#2 1
#3 1
#4 0
#5 0
#6 1
#7 1
#8 0
#9 1
#10 0
Chương trình cài đặt:

#include<iostream>
#include<conio.h>
#define nMax 100
using namespace std;
char matrix[nMax][nMax];
bool isReached;
void visit(char matrix[nMax][nMax], int x,int y){
 if(matrix[x][y] == '3'){
  isReached = true; return;
 }
 matrix[x][y] = '1';
 if(isReached == false && x-1 >=0 && (matrix[x-1][y] == '0' || matrix[x-1][y] == '3')) visit(matrix,x-1,y);
 if(isReached == false && x+1 <nMax && (matrix[x+1][y] == '0' || matrix[x+1][y] == '3')) visit(matrix,x+1,y);
 if(isReached == false && y-1 >=0 && (matrix[x][y-1] == '0' || matrix[x][y-1] == '3')) visit(matrix,x,y-1);
 if(isReached == false && y+1 <nMax && (matrix[x][y+1] == '0' || matrix[x][y+1] == '3')) visit(matrix,x,y+1);
}
int main(){
 freopen("MAZE.INP","r", stdin);
 freopen("MAZE.OUT","w", stdout);
 int testCase;
 int loop =1;
 int beginX, beginY;
 while(loop++ <= 10){
  isReached = false;
  cin>>testCase;
  for(int i=0;i<nMax;i++){
   cin>>matrix[i];
   for(int j=0;j<nMax;j++)
    if(matrix[j][i] == '2'){
     beginX = j; beginY = i;
   }
  }
  visit(matrix,beginX,beginY);
  if(isReached){
   cout<<"#"<<testCase<<" "<<1<<endl;
  }else{
   cout<<"#"<<testCase<<" "<<0<<endl;
  }
  
 }
 return 0;
}

[Baì toán] Tìm đường đi Hamiton ngắn nhất.

[Bài toán] Nhân viên giao bánh piza phải giao bánh cho N khách hàng. Từ cửa hàng bánh , anh ta phải đi giao bánh cho N khách hàng sau đó trở về nhà của mình. Vị trí của của hàng bánh, nhà của anh ta và của khách hàng theo mẫu sau (x,y). Khoảng cách giữa 2 vị trí (x1,y1) và (x2,y2) được tính theo công thức sau: |x1-x2| + |y1-y2|.
Hãy viết chương trình tính đường đi ngắn nhất cho nhân viên trên.
[Input]
Có 10 test case được chứa trong file dữ liệu đầu vào OPTIMALPATH.INP. Dòng đầu ghi số khách hàng N. Dòng sau ghi vị trí (x,y) của văn phòng, nhà của nhân viên và của N khách hàng.
[Output]
Ghi ra file OPTIMALPATH.OUT đường đi ngắn nhất cho mỗi test case. Với mỗi test case được bắt đầu bằng #C.
[I/O example]
5
0 0 100 100 70 40 30 10 10 5 90 70 50 20
6
88 81 85 80 19 22 31 15 27 29 30 10 20 26 5 14
7
22 47 72 42 61 93 8 31 72 54 0 64 26 71 93 87 84 83
8
30 20 43 14 58 5 91 51 55 87 40 91 14 55 28 80 75 24 74 63
9
3 9 100 100 16 52 18 19 35 67 42 29 47 68 59 38 68 81 80 37 94 92
10
39 9 97 61 35 93 62 64 96 39 36 36 9 59 59 96 61 7 64 43 43 58 1 36
10
26 100 72 2 71 100 29 48 74 51 27 0 58 0 35 2 43 47 50 49 44 100 66 96
10
46 25 16 6 48 82 80 21 49 34 60 25 93 90 26 96 12 100 44 69 28 15 57 63
10
94 83 72 42 43 36 59 44 52 57 34 49 65 79 14 20 41 9 0 39 100 94 53 3
10
32 79 0 0 69 58 100 31 67 67 58 66 83 22 44 24 68 3 76 85 63 87 7 86
[Output]
#1 200
#2 304
#3 265
#4 307
#5 306
#6 366
#7 256
#8 399
#9 343
#10 391
Chương trình cài đặt.

#include<iostream>
#define myABS(value) ((value < 0) ? -(value) : (value))
using namespace std;
int matrix[12][12];
int position[12][2];
int minPath;
bool isVisited[12];
int customerNo;
void DFS(int vertice, int pathLength, int verticeCount){
 if(verticeCount == customerNo+1){
  if(pathLength + matrix[vertice][1] < minPath){
   minPath = pathLength + matrix[vertice][1];
  }
  return;
 }
 for(int i=2;i<customerNo+2;i++){
  if(!isVisited[i] && i != vertice && pathLength + matrix[vertice][i] < minPath){
   isVisited[i] = true;
   DFS(i, pathLength + matrix[vertice][i], verticeCount+1);
   isVisited[i] = false;
  }
 }
}
int main(){
 freopen("OPTIMALPATH.INP","r",stdin);
 freopen("OPTIMALPATH.OUT","w", stdout);
 customerNo;
 int tc;
 for(tc=1;tc<=10;tc++){
  cin>>customerNo;
  for(int i=0;i<customerNo + 2;i++){
   cin>>position[i][0]>>position[i][1];
  }
  for(int i=0;i<customerNo+1;i++){
   for(int j=i;j<customerNo+2;j++){
    if(i==j){
     matrix[i][j]=0;
    }else{
     matrix[i][j] = matrix[j][i] =  myABS(position[i][0] - position[j][0]) + myABS(position[i][1] - position[j][1]);
    }
   }
  }
  minPath = 1000000000;
  for(int i=0;i<customerNo+2;i++) isVisited[i] = false;
  isVisited[0] = true;
  DFS(0,0,1);// office's index.
  cout<<"#"<<tc<<" "<<minPath<<endl;
  
 }

 return 0;
}