Trường Đại Học Trà Vinh Khoa Kỹ Thuật Công Nghệ
Chương 2: MÔ TẢ ỨNG DỤNG VÀ GIẢI THÍCH ỨNG DỤNG
CỦA THUẬT TOÁN FLOYD
1. Mô tả ứng dụng
Việc nghiên cứu thuật toán Floyd để áp dụng vào trong thực tế là rất quan
trọng với nhiều tiện lợi cho con người cả về vật chất, của cải lẫn thời gian. Giúp
ích rất nhiều cho con người trong việc nâng cao hiệu quả làm việc và làm tăng
năng suất lao động, tăng thu nhập cho doanh nghiệp.
Qua đây chính là việc áp dụng cho Tài xế Taxi để tìm đường đi ngắn nhất
trong các tuyến đường giao thông đồng thời tiết kiệm được chi phí về nhiên
liệu, thời gian và làm tăng thu nhập cho mình cũng như công ty.
2. Mô tả và giải thích ứng dụng của thuật toán Floyd
Phạm vi áp dụng của thuật toán là Thành Phố Hồ Chí Minh. Ta xem mõi
Quận của Tp.HCM là một đỉnh của đồ thị và các con đường đi từ Quận này
sang Quận kia là đường nối giữa các đỉnh với nhau. Ở đây ta xem đường nối
giữa các Quận là đường 2 chiều.
Lúc đầu ta quản lý một tập hợp động ma trận S đỉnh v và cạnh u (các
Quận trong Tp.HCM là v và đường đi giữa chúng chính là u). với mỗi đỉnh v,
chúng ta quản lý một d[v] là đường đi ngắn nhất trong các đường đi nối hai
Quận bất kỳ của đồ thị.
Ta chỉ xét 13 quận của Tp.HCM là : Quận 12, Quận Tân Phú, Quận Bình
Tân, Quận 6, Quận 5, Quận 4, Quận 2, Quận Bình Thạnh, Quận Gò Vấp, Quận
Tân Bình, Quận 10, Quận 11 và Chợ Bến Thành.

Ta cho đường đi giữa các quận được tính bằng km như sau:
GVHD : Trần Quang Hà trang
1
Trường Đại Học Trà Vinh Khoa Kỹ Thuật Công Nghệ
1. Quận 12
2. Quận Tân Phú
3. Quận Bình Tân

4
6
Trường Đại Học Trà Vinh Khoa Kỹ Thuật Công Nghệ
MA TRẬN
13
0 1 0 0 0 0 0 0 1 2 0 0 0
1 0 2 0 0 0 0 0 0 2 0 0 0
0 2 0 1 0 0 0 0 0 0 1 0 0
0 0 1 0 4 0 0 0 0 0 2 0 0
0 0 0 4 0 2 0 0 0 0 0 3 0
0 0 0 0 2 0 4 0 0 0 0 0 1
0 0 0 0 0 4 0 3 0 0 0 0 1
0 0 0 0 0 0 3 0 2 0 0 0 1
1 0 0 0 0 0 0 2 0 3 0 0 0
2 2 0 0 0 0 0 0 3 0 5 4 2
0 0 1 2 0 0 0 0 0 5 0 1 0
0 0 0 0 3 0 0 0 0 4 1 0 0
0 0 0 0 1 1 1 1 0 2 0 4 0
THUẬT TOÁN FLOYD ÁP DỤNG CHO TÀI XẾ TAXI Ở THÀNH PHỐ
HỒ CHÍ MINH.
#include<stdio.h>
#include<conio.h>
#include <math.h>
#define MAX 50
#define VOCUC 1000
int T[MAX][MAX],L[MAX][MAX],P[MAX][MAX];
GVHD : Trần Quang Hà trang
3
Trường Đại Học Trà Vinh Khoa Kỹ Thuật Công Nghệ
int n,u,v,k;

L[i][j]=T[i][j];
if((i==j) || (L[i][j]==VOCUC))
P[i][j]=0;
else
GVHD : Trần Quang Hà trang
5
Trường Đại Học Trà Vinh Khoa Kỹ Thuật Công Nghệ
P[i][j]=j;
}
}
for(k=1;k<=n;k++)
{
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(L[i][j]>(L[i][k]+L[k][j]))
{
L[i][j]=L[i][k]+L[k][j];
P[i][j]=P[i][k];
}
}
}
}
}
GVHD : Trần Quang Hà trang
6
Trường Đại Học Trà Vinh Khoa Kỹ Thuật Công Nghệ
VÍ DỤ CHO THUẬT TOÁN FLOYD
Ví dụ:

P[2][4]=0
P[2][5]=0
Tang i=3
P[3][1]=0
P[3][2]=2
P[3][3]=0
P[3][4]=3
P[3][5]=0
Tang i=4
P[4][1]=1
P[4][2]=0
P[4][3]=3
GVHD : Trần Quang Hà trang
7
Trường Đại Học Trà Vinh Khoa Kỹ Thuật Công Nghệ
P[4][4]=0
P[4][5]=5
Tang i=5
P[5][1]=0
P[5][2]=0
P[5][3]=3
P[5][4]=0
P[5][5]=0
Chay xong dong for nay ta duoc ma tran L va P
0 1 5 1000 1000
2 0 3 1000 1000
1000 2 0 1 1000
-2 0 2 0 2
1000 1000 3 1000 0
0 2 3 0 0