Floyd - Warshall

// Chương trình tìm đường đi ngắn nhất bằng thuật toán Floyd - Warshall
#include <iostream>
#include <fstream>

using namespace std;

#define INF INT_MAX

void importFile(char *file_input_name, int **&Graph, int &vertexNumber);
void FloydWarshall(int **Graph, int vertexNumber, int **dist, int **next);

void main()
{
int vertexNumber;  // Số đỉnh
int **Graph;       // Ma trận trọng số
importFile("input.txt", Graph, vertexNumber);  // Nhập vào ma trận
int startVer = 0;                              // Giả sử đỉnh bắt đầu là 0
int goalVer = vertexNumber-1;                  // Giả sử đỉnh kết thúc là n-1

// Khởi tạo các mảng
int **dist = new int*[vertexNumber];    // int **dist: mảng chứa các độ dài đường đi ngắn nhất
int **next = new int*[vertexNumber];    // int **next: mảng chứa các đỉnh tiếp theo trong đường đi
for(int i = 0; i < vertexNumber; ++i)
{
dist[i] = new int[vertexNumber];
next[i] = new int[vertexNumber];
}

// Tìm đường đi ngắn nhất
FloydWarshall(Graph, vertexNumber, dist, next);

// In đường đi ngắn nhất
cout << "Duong di ngan nhat tu " << startVer+1 << " den " << goalVer+1 << " co do dai " << dist[startVer][goalVer] << " la:" << endl;
int k = startVer;
cout << startVer+1;
do
{
k = next[k][goalVer];
cout << " -> " << k+1;
} while (k != goalVer);

// Xóa con trỏ sau khi sử dụng
for(int i = 0; i < vertexNumber; ++i)
{
delete []dist[i];
delete []next[i];
}

delete []dist;
delete []next;
}

/// THUẬT TOÁN FLOYD - WARSHALL ĐỂ TÌM ĐƯỜNG ĐI NGẮN NHẤT
void FloydWarshall(int **Graph, int vertexNumber, int **dist, int **next)
{
/* == BƯỚC 1 ==*/
/* KHỞI TẠO */
for (int i = 0; i < vertexNumber; ++i)
{
for(int j = 0; j < vertexNumber; ++j)
{
if(i == j)
dist[i][j] = 0;
else
{

// Lưu ý: Theo đúng tư tưởng thuật toán,
// các đỉnh i, j không có cạnh nối trong ma trận trọng số
// sẽ quy ước giá trị M[i][j] = INF.
// Tuy nhiên, để đơn giản,
// ta có thể coi như không có trường hợp
// cạnh có trọng số bằng 0 và quy ước giá trị M[i][j] = 0
// cho các đỉnh i, j không kề nhau.
if(Graph[i][j] != 0)
{
dist[i][j] = Graph[i][j];
next[i][j] = j;
}
else
{
dist[i][j] = INF;
next[i][j] = -1;
}
}
}
}

/* == BƯỚC 2 == */
// Với mọi k = 1, 2, ..., n
for(int k = 0; k < vertexNumber; ++k)
{
// Với mọi đỉnh i, j
for(int i = 0; i < vertexNumber; ++i)
{
for(int j = 0; j < vertexNumber; ++j)
{
if((dist[i][k] != INF && dist[k][j] != INF && k != j) && (dist[i][j] > dist[i][k] + dist[k][j]))
{
dist[i][j] = dist[i][k] + dist[k][j];
next[i][j] = k;
}
}
}
}
}

// Đọc một ma trận
void importFile(char *file_input_name, int **&Graph, int &vertexNumber)
{
ifstream inFile(file_input_name);

if (inFile.is_open())
{
inFile >> vertexNumber;   // Đọc số lượng đỉnh
int **WeightMatrix = new int*[vertexNumber];
for (int t = 0; t < vertexNumber; t++)
{
WeightMatrix[t] = new int[vertexNumber];
}

for (int i = 0; i < vertexNumber; i++)
{
for (int j = 0; j < vertexNumber; j++)
{
inFile >> WeightMatrix[i][j];
}
}
Graph = WeightMatrix;
inFile.close();
}
else
cout << "Unable to open file";
}