Bài 03: CÀI ĐẶT CHƯƠNG TRÌNH THUẬT TÓAN FLOY-WARSHALL TÌM ĐƯỜNG ĐI NGẮN NHẤT GIỮA CẶP ĐỈNH BẰNG NGÔN NGỮ C
III.1 Bài tóan
Cài đặt chương trình thuật tóan Floyd –Warshall tìm đường đi ngắn nhất ở mọi cặp đỉnh giữa mọi cặp đỉnh bằng ngôn ngữ C.
File cấu trúc dữ liệu vào FLOYDWAR.INF có cấu trúc
n m n: số đỉnh, m: số cung, a: đỉnh đầu, e: đỉnh cuối
đỉnh đầu, đỉnh cuối, trọng số
………………
…………………….
q p số đỉnh,số cung, đỉnh đầu, đỉnh cuối
đỉnh đầu, đỉnh cuối, trọng số
………………
…………………….
File kết quả: FLOYDWAR.OUT
D (Ma trận độ dài đường đi ngắn nhất giữa mọi cặp đỉnh)
……….
P (Ma trận xác định đường đi ngắn nhất giữa mọi cặp đỉnh)
Ví dụ:
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
#include
intn; /* Then number of nodes */
intdist[16][16]; /* dist[i][j] is the length of the edge between i and j if
it exists, or 0 if it does not */
voidprintDist() {
int i, j;
printf(" ");
for (i = 0; i < n; ++i)
printf("%4c", 'A' + i);
printf("\n");
for (i = 0; i < n; ++i) {
printf("%4c", 'A' + i);
for (j = 0; j < n; ++j)
printf("%4d", dist[i][j]);
printf("\n");
}
printf("\n");
}
/*
floyd_warshall()
after calling this function dist[i][j] will the the minimum distance
between i and j if it exists (i.e. if there's a path between i and j)
or 0, otherwise
*/
voidfloyd_warshall() {
int i, j, k;
for (k = 0; k < n; ++k) {
printDist();
for (i = 0; i < n; ++i)
for (j = 0; j < n; ++j)
/* If i and j are different nodes and if
the paths between i and k and between
k and j exist, do */
if ((dist[i][k] * dist[k][j] != 0) && (i != j))
/* See if you can't get a shorter path
between i and j by interspacing
k somewhere along the current
path */
if ((dist[i][k] + dist[k][j] < dist[i][j]) ||
(dist[i][j] == 0))
dist[i][j] = dist[i][k] + dist[k][j];
}
printDist();
}
intmain(int argc, char *argv[]) {
FILE *fin = fopen("dist.txt", "r");
fscanf(fin, "%d", &n);
int i, j;
for (i = 0; i < n; ++i)
for (j = 0; j < n; ++j)
fscanf(fin, "%d", &dist[i][j]);
fclose(fin);
floyd_warshall();
return 0;
}
II.2. Cài đặt bằng ngôn ngữ C/Java
// Floyd-Warshall algorithm - iterative version
//
// Author: Nguyen Minh Nhat
// Ngay: 04,2018 .
public class FloydWarshallIter {
int numVertices; // Số đỉnh khi khởi tạo
double[][] adjMatrix; // Ma trận kề (given as input).
double[][] D;
public void initialize (int numVertices)
{
this.numVertices = numVertices;
// Khởi tạo ma trận Dk
D = new double [numVertices][];
for (int i=0; i < numVertices; i++){
D[i] = new double [numVertices];
}
}
public void allPairsShortestPaths (double[][] adjMatrix)
{
// D = trọng số khi k = -1
for (int i=0; i
for (int j=0; j
if (i != j) {
if (adjMatrix[i][j] > 0)
D[i][j] = adjMatrix[i][j];
else
D[i][j] = Double.MAX_VALUE;
}
else {
// CHú ý: Chúng ta nhận D[i][j] = 0 hoặc không thể
D[i][j] = 0;
}
}
}
// Chúng tôi sẽ dừng lại khi không có những sự thay đổi về sau
// Bởi vậy, chúng tôi cần một biến để theo dõi whether Một Được thay đổi được xảy ra
boolean changeOccurred = true;
// Lặp lại không cho đến nhiều sự thay đổi hơn nào.
while (changeOccurred) {
changeOccurred = false;
for (int i=0; i
for (int d=0; d
if (i != d) {
// Cho giá trị nhỏ nhất giữa i và d, xem xét những lân cận j
for (int j=0; j
if ( (j != i) && (adjMatrix[i][j] > 0) ) {
/ / Nếu nó tốt hơn hơn j,thì quay lại giá trị mới phí mới
if (D[j][d] + adjMatrix[i][j] < D[i][d]) {
D[i][d] = D[j][d] + adjMatrix[i][j];
changeOccurred = true;
}
}
} // kết thúc end-inner-for
} //end if
} //end-for
} // end-for
} // end-while
// Có thể viết thêm cấu trúc đường đi ngắn nhất
}
public static void main (String[] argv)
{
// Nhập trực tiếp một trường hợp cho mang A để test
double[][] adjMatrix = {
{0, 1, 7, 0, 5, 0, 1},
{1, 0, 1, 0, 0, 7, 0},
{7, 1, 0, 1, 7, 0, 0},
{0, 0, 1, 0, 1, 0, 0},
{5, 0, 7, 1, 0, 1, 0},
{0, 7, 0, 0, 1, 0, 1},
{1, 0, 0, 0, 0, 1, 0},
};
int n = adjMatrix.length;
FloydWarshallIter fwAlg = new FloydWarshallIter ();
fwAlg.initialize (n);
fwAlg.allPairsShortestPaths (adjMatrix);
//Có thể viết thêm để in ra đường dẫn
}
}end programming