Dijkstra

#include <fstream>
#include <iostream>

using namespace std;

#define INF INT_MAX

void importFile(char *file_input_name, int **&Graph, int &verNum);
void Dijkstra(int **Graph, int verNum, int starVer, int goalVer, int *&B, int *&L, int *&T);

void main()
{
// Nhập ma trận kề của đồ thị
int **Graph; // Ma trận trọng số (Weight Matrix)
int verNum;  // Số lượng đỉnh (vertex number)
importFile("input.txt", Graph, verNum);

int startVer = 0;             // Giả sử đỉnh bắt đầu là 0
int goalVer = verNum-1;       // Giả sử đỉnh kết thúc là n-1

// Khởi tạo các mảng
int *T = new int[verNum];     // *T : Mảng đánh đấu xem đỉnh i có thuộc T hay không
int *B = new int[verNum];     // *B: mảng chứa các đỉnh trên đường đi
int *L = new int[verNum];     // *L: mảng chứa độ dài đường đi

// Dijkstra Algorithm
Dijkstra(Graph, verNum, startVer, goalVer, B, L, T);

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

// Xóa các con trỏ đã dùng
delete []B;
delete []L;
delete []T;
for (int i = 0; i < verNum; i++)
{
delete []Graph[i];
}
delete []Graph;
}

/// THUẬT TOÁN DIJKSTRA ĐỂ TÌM ĐƯỜNG ĐI NGẮN NHẤT
void Dijkstra(int **Graph, int verNum, int startVer, int goalVer, int *&B, int *&L, int *&T)
{
// Tìm đường đi ngắn nhất
/* == BƯỚC 1 ==*/
for (int i = 0; i < verNum; ++i)
{
T[i] = 1; // Gán T = V
L[i] = INF; // Gán L[i] = VOCUC với mọi đỉnh i
B[i] = -1; // Gán B[i] = -1 với mọi đỉnh i
}
L[startVer] = 0; // Gán L[s] = 0

/* == BƯỚC 2: Kiểm tra g có còn thuộc T hay không == */
while(T[goalVer] == 1)
{
/* == BƯỚC 3: Chọn đỉnh i thuộc T sao cho L[i] nhỏ nhất và gán T = T\{i} == */
int Lmin = INF; // Lưu giá trị L[i] nhỏ nhất
int iMin = INF; // Lưu chỉ số đỉnh có L[i] nhỏ nhất
// Duyệt qua tìm giá trị Lmin
for(int i = 0; i < verNum; ++i)
{
// Kiểm tra đỉnh i có thuộc T hay không và so sánh tìm giá trị L[i] nhỏ nhất
if(T[i] == 1 && L[i] < Lmin)
{
Lmin = L[i];
iMin = i;
}
}
T[iMin] = 0; // gán T = T\{i} với i=iMin có L[i]=Lmin nhỏ nhất tìm được

/* == BƯỚC 4: Với mọi j thuộc T và có cạnh nối đến i=iMin == */
for(int j = 0; j < verNum; ++j)
{
if((T[j] == 1 && Graph[iMin][j] != INF) && (L[j] == INF || L[j] > L[iMin] + Graph[iMin][j]))
{
L[j] = L[iMin] + Graph[iMin][j];
B[j] = iMin;
}
}

/*== BƯỚC 5: Quay lại bước 2 ==*/
}

/*== BƯỚC 6: Dừng thuật toán ==*/
}

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

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

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