[Algorithms] Shortest Path - Dijsktra using Heap

<-------------------HEAP-------------------->
#include "Heap.h"

/*
SẮP XẾP LẠI HEAP SAO CHO THỎA MÃN TÍNH CHẤT MIN HEAP
-Đầu vào: Danh sách Heap, vị trí của nút
-Đầu ra: Không có
*/
void Heapify(iVPair &heap, int i) {
int left = (2 * i) + 1;
int right = (2 * i) + 2;
int smallest = i;
//So sánh với con bên trái
if (left < heap.size() && heap[left].second < heap[smallest].second) {
smallest = left;
}
//So sánh với con bên phải
if (right < heap.size() && heap[right].second < heap[smallest].second) {
smallest = right;
}
//Đổi chỗ
if (smallest != i) {
swap(heap[i], heap[smallest]);
Heapify(heap, smallest);
}
}
/*
THÊM NÚT VÀO HEAP
-Đầu vào: Danh sách Heap, đỉnh cần thêm, khoảng cách từ a tới đỉnh đó
-Đầu ra: Không có
*/

void pushHeap(iVPair &heap, int x, int dx) {
heap.push_back({ x,dx });
int i = heap.size() - 1;
//Sắp xếp lại Heap sau khi thêm
while (i != 0 && heap[i].second < heap[(i - 1) / 2].second) {
swap(heap[i], heap[(i - 1) / 2]);
i = (i - 1) / 2;
}
}
/*
LẤY VÀ XÓA NÚT NHỎ NHẤT (ĐỈNH) CỦA HEAP
-Đầu vào: Danh sách Heap
-Đầu ra: Không có
*/
int popHeap(iVPair &heap) {
if (heap.size() <= 0) return INT_MAX;
int root = heap[0].first;     //lấy đỉnh tại nút gốc
if (heap.size() > 1) {
swap(heap[0], heap[heap.size() - 1]);
}
heap.pop_back();
if (heap.size() == 0) return root;
//Sắp xếp lại Heap sau khi xóa
Heapify(heap, 0);
return root;
}



<---------------DIJSKTRA---------------->
#include "Graph.h"
#include "Heap.h"

/*
MỞ FILE ĐỂ ĐỌC ĐỒ THỊ
-Đầu vào: Đồ thị G, điểm bắt đầu a, điểm kết thúc b
-Đầu ra: Không có
*/
void loadGraph(Graph &G, int &a, int &b) {
ifstream file("input.txt");
int _n, _m, _a, _b;
file >> _n >> _m >> _a >> _b;
G.n = _n;
a = _a;
b = _b;
G.adj = new iVPair[G.n + 1];
int u, v, w;
for (int i = 0; i < _m; i++) {
file >> u >> v >> w;
//ĐỒ THỊ VÔ HƯỚNG
G.adj[u].push_back({ v,w });
G.adj[v].push_back({ u,w });
}
file.close();
}
/*
THUẬT TOÁN DIJKSTRA SỬ DỤNG HEAP
-Đầu vào: Đồ thị G, Heap, danh sách khoảng cách từ a tới đỉnh khác d, danh sách đỉnh đi trace, điểm bắt đầu a, điểm kết thúc b
-Đầu ra: Không có
*/
void dijkstra(Graph G, iVPair heap, iVect &d, int a, int b) {
bVect free(G.n + 1, true);
pushHeap(heap, a, d[a]);          //Thêm nút đầu tiên vào Heap
while (heap.size() > 0) {
int u = popHeap(heap);          //Lấy đỉnh kế có khoảng cách nhỏ nhất
if (u == b) break;         //Nếu đỉnh đang xét là đỉnh đích thì dừng
free[u] = false;             //đánh dấu đã xét
for (auto next : G.adj[u]) {            //Duyệt các đỉnh kề
if (free[next.first] && d[next.first] > next.second + d[u]) {
d[next.first] = next.second + d[u];        //Cập nhật lại nút
pushHeap(heap, next.first, next.second);        //Thêm đỉnh vào heap
}
}
}
}