Dijkstra
Sử dụng cấu trúc Pairing Heap để lưu trữ và sử lý dữ liệu. Sử dụng thuật toán Dijkstra để tìm đường đi ngắn nhấtunknown
c_cpp
16 days ago
31 kB
7
Indexable
// Chương trình này sử dụng c++17. Nhóm sử dụng gcc để biên dịch nên yêu cầu gcc tối thiểu 11.x (tại đây là 13.x) #include <iostream> #include <fstream> #include <sstream> #include <string> #include <vector> #include <limits> // Thư viện cho numeric_limits (ví dụ: numeric_limits<double>::max()) #include <chrono> #include <filesystem> // Thư viện thao tác với hệ thống tệp (lấy tên file, thư mục, ...) #include <algorithm> // Thư viện chứa các hàm xử lý thuật toán (như reverse) #include <iomanip> // Thư viện để định dạng số khi in (std::fixed, std::setprecision) #include <locale> // Thư viện xử lý locale (để đọc số thực đúng với ký hiệu dấu chấm) using namespace std; // Sử dụng bí danh - cụ thể là: std::filesystem::path filePath = std::filesystem::current_path(); // là 1 namespace chứa các hàm, lớp để đọc/ghi tệp - yêu cầu: thư viện <filesystem> namespace fs = std::filesystem; // --- Cấu Trúc Dữ Liệu Pairing Heap --- // Định nghĩa cấu trúc Node cho Pairing Heap struct PairingHeapNode { double key; // Giá trị ưu tiên (ở đây là khoảng cách, kiểu double) int value; // Thông tin đỉnh, cụ thể là chỉ số của đỉnh PairingHeapNode* child; // Con trỏ trỏ đến con đầu tiên của node này PairingHeapNode* sibling; // Con trỏ trỏ đến node anh em kế tiếp PairingHeapNode* parent; // Con trỏ trỏ đến node cha (hữu ích khi dùng decreaseKey) // Hàm dựng: khởi tạo node với key và value cho trước, các con trỏ được khởi tạo ban đầu là nullptr. PairingHeapNode(double k, int val) : key(k), value(val), child(nullptr), sibling(nullptr), parent(nullptr) {} // Destructor mặc định: vì việc quản lý bộ nhớ cho cấu trúc này được thực hiện ở lớp PairingHeap. ~PairingHeapNode() = default; }; // Định nghĩa lớp Pairing Heap class PairingHeap { public: PairingHeapNode* root; // Con trỏ trỏ đến nút gốc của heap // Constructor: khởi tạo heap rỗng, gốc được đặt là nullptr. PairingHeap() : root(nullptr) {} // Destructor: giải phóng bộ nhớ của tất cả các node còn lại trong heap khi đối tượng heap bị hủy. ~PairingHeap() { destroyHeap(root); } // Hàm destroyHeap: hàm đệ quy để giải phóng bộ nhớ các node của heap. // Nó duyệt theo đệ quy từ node gốc sang các node con, rồi các node anh em. void destroyHeap(PairingHeapNode* node) { if (!node) return; // Nếu node rỗng, dừng lại destroyHeap(node->child); // Giải phóng bộ nhớ cho cây con (đệ quy) destroyHeap(node->sibling); // Giải phóng bộ nhớ cho các node anh em delete node; // Xóa node hiện tại } // Hàm merge: trộn (hoặc hợp nhất) hai cây heap h1 và h2 // Nếu một trong hai cây rỗng, trả về cây còn lại // Nếu cả hai đều không rỗng, so sánh key của gốc và trả về cây có key nhỏ nhất làm gốc. PairingHeapNode* merge(PairingHeapNode* h1, PairingHeapNode* h2) { if (!h1) return h2; // Nếu h1 rỗng, trả về h2 if (!h2) return h1; // Nếu h2 rỗng, trả về h1 // So sánh khóa của hai gốc: nếu khóa của h1 nhỏ hơn hoặc bằng h2, // thì h1 trở thành gốc của cây hợp nhất. if (h1->key <= h2->key) { h2->parent = h1; // Đặt cha của h2 là h1 h2->sibling = h1->child; // Gán h2 là anh em kế tiếp của con đầu tiên của h1 h1->child = h2; // Cập nhật con đầu tiên của h1 là h2 return h1; // Trả về h1 làm gốc của cây mới } else { // Nếu không, h2 có khóa nhỏ hơn, nên h2 trở thành gốc h1->parent = h2; // Đặt cha của h1 là h2 h1->sibling = h2->child; // Gán h1 là anh em kế tiếp của con đầu tiên của h2 h2->child = h1; // Cập nhật con đầu tiên của h2 là h1 return h2; // Trả về h2 làm gốc mới } } // Hàm insert: chèn một node mới vào heap với giá trị key và value cho trước. // Tạo ra một node mới (dạng heap gồm 1 node), rồi trộn (merge) nó vào heap hiện tại. // Trả về con trỏ đến node vừa được chèn, để có thể dùng cho thao tác decreaseKey sau này. PairingHeapNode* insert(double key, int value) { PairingHeapNode* node = new PairingHeapNode(key, value); root = merge(root, node); if (root) root->parent = nullptr; // Đảm bảo rằng node gốc không có cha return node; } // Hàm kiểm tra heap có rỗng hay không bool empty() const { return root == nullptr; } // Hàm getMin: trả về cặp {key, value} của node có key nhỏ nhất (node gốc) mà không xóa nó khỏi heap. pair<double, int> getMin() const { if (root) return {root->key, root->value}; // Nếu heap rỗng, trả về cặp giá trị mặc định (key lớn nhất và value không hợp lệ) return {numeric_limits<double>::max(), -1}; } // Hàm deleteMin: xóa node gốc (node có key nhỏ nhất) khỏi heap và trả về cặp {key, value} của nó. pair<double, int> deleteMin() { if (!root) return {numeric_limits<double>::max(), -1}; // Nếu heap rỗng PairingHeapNode* oldRoot = root; // Lưu lại node gốc cũ để giải phóng bộ nhớ sau pair<double, int> ret = {root->key, root->value}; // Lưu giá trị trả về // Nếu node gốc không có con, sau khi xóa heap sẽ rỗng. if (!root->child) { root = nullptr; } else { // Nếu có con, thực hiện merge các cây con của gốc theo quy tắc merge theo cặp (two-pass merge) root = mergePairs(root->child); if (root) root->parent = nullptr; // Đảm bảo node gốc mới không có cha } delete oldRoot; // Giải phóng bộ nhớ của node gốc cũ return ret; // Trả về cặp {key, value} của node đã xóa } // Hàm mergePairs: hợp nhất các node anh em theo cặp (được sử dụng trong deleteMin) // Đầu vào là con trỏ tới danh sách các anh em cần merge. // Nếu danh sách rỗng hoặc chỉ có một node, trả về node đó. // Nếu có nhiều hơn một node, thực hiện merge theo cặp sau đó merge kết quả. PairingHeapNode* mergePairs(PairingHeapNode* firstSibling) { if (!firstSibling) return nullptr; // Nếu danh sách rỗng, trả về nullptr if (!firstSibling->sibling) { firstSibling->parent = nullptr; // Nếu chỉ có một node, đảm bảo nó không có cha return firstSibling; } // Đặt 2 node đầu tiên của danh sách làm cặp a và b PairingHeapNode* a = firstSibling; PairingHeapNode* b = firstSibling->sibling; PairingHeapNode* rest = b->sibling; // Phần còn lại của danh sách anh em // Ngắt kết nối a và b với danh sách ban đầu: a->sibling = nullptr; a->parent = nullptr; b->sibling = nullptr; b->parent = nullptr; // Merge cặp đầu tiên (a và b) thành một cây mới. PairingHeapNode* merged_ab = merge(a, b); // Đệ quy merge phần còn lại của danh sách. PairingHeapNode* merged_rest = mergePairs(rest); // Merge kết quả của merge cặp đầu tiên với kết quả của phần còn lại. return merge(merged_ab, merged_rest); } // Hàm decreaseKey: giảm khóa (key) của một node đã cho xuống giá trị newKey. // Điều kiện: newKey phải nhỏ hơn key hiện tại của node. // Sau khi giảm khóa, ta cần tách node ra khỏi vị trí cũ của nó trong cây rồi trộn vào heap lại. void decreaseKey(PairingHeapNode* node, double newKey) { if (!node || newKey >= node->key) { return; // Nếu node rỗng hoặc newKey không nhỏ hơn key cũ, không làm gì cả. } // Cập nhật giá trị key mới cho node. node->key = newKey; // Nếu node là gốc, việc giảm khóa chỉ cần cập nhật giá trị key. if (node == root) { return; } // --- Bước tách node khỏi cây hiện tại --- PairingHeapNode* nodeParent = node->parent; if (nodeParent != nullptr) { // Kiểm tra nếu node là con đầu tiên của cha if (nodeParent->child == node) { nodeParent->child = node->sibling; // Cập nhật con của cha là node kế tiếp } else { // Nếu node không phải con đầu tiên, tìm node đứng ngay trước node đó trong danh sách con của cha. PairingHeapNode* prevSibling = nodeParent->child; while (prevSibling != nullptr && prevSibling->sibling != node) { prevSibling = prevSibling->sibling; } if (prevSibling != nullptr) { prevSibling->sibling = node->sibling; // Loại bỏ node khỏi danh sách anh em } } } // Ngắt kết nối node hoàn toàn (không có cha, không có anh em) node->parent = nullptr; node->sibling = nullptr; // --- Trộn node đã được tách vào heap chính --- root = merge(root, node); if (root) root->parent = nullptr; // Đảm bảo lại node gốc không có cha } }; // --- Thuật Toán Dijkstra sử dụng Pairing Heap --- // // Hàm dijkstra tính khoảng cách ngắn nhất từ đỉnh start đến tất cả các đỉnh khác của đồ thị. // Đồ thị được biểu diễn dưới dạng danh sách kề (vector các vector chứa cặp {đỉnh_kề, trọng_số}). // Kết quả được trả về qua tham chiếu ở vector dist (khoảng cách) và prev (đỉnh đi trước dùng để tái tạo đường đi). // void dijkstra(const vector<vector<pair<int, double>>>& graph, int start, vector<double>& dist, vector<int>& prev) { int n = graph.size(); // Số lượng đỉnh của đồ thị // Khởi tạo vector dist và prev: // - dist: tất cả các khoảng cách ban đầu được gán là vô cùng (numeric_limits<double>::max()) // - prev: tất cả các đỉnh trước được gán là -1 (chưa xác định) dist.assign(n, numeric_limits<double>::max()); prev.assign(n, -1); // Đặt khoảng cách từ đỉnh start đến chính nó là 0 dist[start] = 0.0; // Tạo một Pairing Heap rỗng để sử dụng trong thuật toán PairingHeap heap; // Vector heapNodes sẽ lưu các con trỏ đến các node trong heap, để thuận tiện cho việc gọi decreaseKey vector<PairingHeapNode*> heapNodes(n, nullptr); // Chèn tất cả các đỉnh vào heap: // - Đỉnh start có khoảng cách ban đầu 0.0 // - Các đỉnh khác có khoảng cách ban đầu là vô cùng for (int i = 0; i < n; i++) { if (i == start) heapNodes[i] = heap.insert(0.0, i); else heapNodes[i] = heap.insert(numeric_limits<double>::max(), i); } // Vòng lặp chính của Dijkstra: chạy đến khi heap rỗng. while (!heap.empty()) { // Lấy đỉnh u có khoảng cách d nhỏ nhất (node gốc của heap) và xóa nó khỏi heap. auto [d, u] = heap.deleteMin(); // Nếu d là vô cùng, nghĩa là các đỉnh còn lại không thể tiếp cận được từ start -> dừng thuật toán. if (d >= numeric_limits<double>::max() - 1.0) break; // Kiểm tra tối ưu: nếu khoảng cách d lấy ra lớn hơn khoảng cách đã biết tốt nhất (dist[u]) thì bỏ qua. if (d > dist[u] && dist[u] != numeric_limits<double>::max()) { continue; } // Duyệt qua tất cả các cạnh xuất phát từ đỉnh u. for (const auto& edge : graph[u]) { int v = edge.first; // Lấy đỉnh kề double weight = edge.second; // Lấy trọng số của cạnh (u, v) // --- Bước "Relaxation" (Nới lỏng cạnh) --- // Kiểm tra xem qua đỉnh u có cho đường đi ngắn hơn đến v không. // Cần đảm bảo dist[u] không phải vô cùng trước khi cộng với weight. if (dist[u] != numeric_limits<double>::max() && dist[u] + weight < dist[v]) { // Nếu tìm thấy đường đi ngắn hơn: // 1. Cập nhật khoảng cách từ start đến v dist[v] = dist[u] + weight; // 2. Ghi nhận đỉnh u là đỉnh đi trước của v trên đường đi ngắn nhất vừa tìm được prev[v] = u; // 3. Gọi hàm decreaseKey trên node tương ứng với đỉnh v trong heap heap.decreaseKey(heapNodes[v], dist[v]); } } } } // Hàm reconstruct_path: tái tạo đường đi ngắn nhất từ đỉnh start đến đỉnh end // Dựa vào vector prev được cập nhật trong thuật toán Dijkstra. vector<int> reconstruct_path(int start, int end, const vector<int>& prev) { vector<int> path; // Vector lưu trữ các đỉnh tạo thành đường đi (đầu tiên theo thứ tự đảo ngược) int current = end; // Bắt đầu từ đỉnh kết thúc // Duyệt ngược từ đỉnh end về đến đỉnh start while (current != -1) { path.push_back(current); // Thêm đỉnh hiện tại vào đường đi if (current == start) // Nếu đã về đến đỉnh start, dừng vòng lặp break; current = prev[current]; // Di chuyển sang đỉnh đi trước } // Kiểm tra xem đường đi có hợp lệ không: nếu vector path rỗng hoặc đỉnh cuối cùng không phải start thì trả về rỗng. if (path.empty() || path.back() != start) { return {}; // Không tìm thấy đường đi hợp lệ } // Vì path được lưu theo thứ tự ngược (từ end về start), ta đảo ngược lại trước khi trả về reverse(path.begin(), path.end()); return path; } // --- Hàm Main --- // // Trong hàm main, chương trình thực hiện các bước sau: // 1. Liệt kê các file .txt trong thư mục hiện hành và cho phép người dùng chọn file. // 2. Đọc dữ liệu từ file theo định dạng: dòng đầu tiên là số đỉnh, các dòng sau là thông tin cạnh // theo định dạng "u, v, w" (các giá trị cách nhau bởi dấu phẩy). // 3. Xây dựng đồ thị dưới dạng danh sách kề. // 4. Nhập vào đỉnh bắt đầu và đỉnh kết thúc từ bàn phím. // 5. Thực hiện thuật toán Dijkstra và đo thời gian thực hiện (nếu người dùng yêu cầu). // 6. Tái tạo và in ra đường đi ngắn nhất cùng khoảng cách tổng. int main() { // In lời chào cout << "============================================\n"; cout << " Chuong trinh tim duong di ngan nhat\n"; cout << " Su dung thuat toan Dijkstra & Pairing Heap\n"; cout << "============================================\n"; // ---- Phần liệt kê và chọn file ---- vector<string> txtFiles; // Vector lưu tên các file .txt có trong thư mục hiện hành vector<fs::path> txtFilePaths; // Lưu đường dẫn đầy đủ của file try { cout << "Dang quet thu muc hien tai (" << fs::current_path().string() << ") de tim file .txt...\n"; // Duyệt qua tất cả các mục trong thư mục hiện hành for (const auto& entry : fs::directory_iterator(fs::current_path())) { // Kiểm tra nếu đây là file thông thường và có phần mở rộng là .txt if (entry.is_regular_file() && entry.path().extension() == ".txt") { // Lấy tên file (không bao gồm đường dẫn) và thêm vào vector txtFiles.push_back(entry.path().filename().string()); txtFilePaths.push_back(entry.path()); // Lưu đường dẫn đầy đủ } } } catch (const fs::filesystem_error& e) { // Nếu có lỗi truy cập thư mục, thông báo nhưng vẫn cho phép nhập đường dẫn thủ công cerr << "Loi khi truy cap thu muc hien tai: " << e.what() << endl; cerr << "Ban van co the nhap duong dan file truc tiep.\n"; } string fileName = ""; // Biến lưu tên file hoặc đường dẫn file được chọn // Chỉ hiển thị danh sách nếu tìm thấy file if (!txtFiles.empty()) { cout << "\nDanh sach file .txt tim thay:" << endl; for (size_t i = 0; i < txtFiles.size(); ++i) { cout << i + 1 << ": " << txtFiles[i] << endl; } cout << "\nChon file bang cach nhap so thu tu, hoac nhap duong dan day du toi file: "; } else { cout << "\nKhong tim thay file .txt nao trong thu muc hien tai." << endl; cout << "Vui long nhap duong dan day du toi file du lieu: "; } string userInput; // Sử dụng getline để đọc cả dòng, cho phép đường dẫn chứa khoảng trắng // >> ws để bỏ qua các khoảng trắng/newline còn sót lại từ các lệnh cin trước (nếu có) getline(cin >> ws, userInput); bool fileSelected = false; // Cờ để kiểm tra xem file đã được chọn hợp lệ chưa // Thử xử lý input như một số thứ tự try { size_t charsProcessed; // Biến để kiểm tra xem stoi có xử lý toàn bộ chuỗi không int choice = stoi(userInput, &charsProcessed); // Kiểm tra xem toàn bộ chuỗi nhập vào có phải là số không và số đó có hợp lệ không if (charsProcessed == userInput.length()) { if (choice >= 1 && choice <= static_cast<int>(txtFiles.size())) { // Lựa chọn số hợp lệ fileName = txtFilePaths[choice - 1].string(); // Lấy đường dẫn đầy đủ từ vector paths cout << "=> Da chon file tu danh sach: " << txtFiles[choice - 1] << " (" << fileName << ")" << endl; fileSelected = true; } else if (!txtFiles.empty()) { // Số nhập vào không nằm trong phạm vi danh sách cout << "=> Lua chon so thu tu khong hop le." << endl; // Không đặt fileSelected = true, sẽ rơi vào trường hợp xử lý như đường dẫn } // Nếu txtFiles rỗng, việc nhập số cũng sẽ được coi là đường dẫn } // Nếu charsProcessed != userInput.length(), nghĩa là chuỗi không hoàn toàn là số (vd: "1abc") // -> sẽ rơi vào khối catch hoặc xử lý như đường dẫn bên dưới. } catch (const std::invalid_argument&) { // Không phải là số -> Chắc chắn là đường dẫn } catch (const std::out_of_range&) { // Số quá lớn -> Coi như đường dẫn (ít khả năng xảy ra) } // Nếu không chọn được file từ số thứ tự, coi userInput là đường dẫn if (!fileSelected) { fileName = userInput; // Gán trực tiếp input làm tên file/đường dẫn cout << "=> Dang xu ly '" << fileName << "' nhu mot file." << endl; fileSelected = true; // Tạm thời coi là đã chọn, sẽ kiểm tra tồn tại sau } // --- Kiểm tra sự tồn tại và mở file --- if (!fileSelected || fileName.empty()) { cout << "Chua chon file nao hop le. Thoat chuong trinh." << endl; return 1; } // Kiểm tra xem đường dẫn file có tồn tại và là file thông thường không try { if (!fs::exists(fileName)) { cout << "Loi: File hoac duong dan '" << fileName << "' khong ton tai." << endl; return 1; } if (!fs::is_regular_file(fileName)) { cout << "Loi: Duong dan '" << fileName << "' khong phai la mot file thong thuong." << endl; return 1; } } catch (const fs::filesystem_error& e) { cerr << "Loi khi kiem tra file: " << e.what() << endl; return 1; } // Mở file để đọc dữ liệu ifstream infile(fileName); if (!infile) { cout << "Khong mo duoc file: " << fileName << endl; return 1; } cout << "Mo file '" << fileName << "' thanh cong\n"; // ---- Phần đọc file và xây dựng đồ thị ---- // Đọc dòng đầu tiên của file: chứa số đỉnh của đồ thị. string line; int n = 0; // Khởi tạo số lượng đỉnh là 0. if (getline(infile, line)) { try { n = stoi(line); // Chuyển đổi dòng đọc được thành số nguyên. } catch (const std::invalid_argument& e) { cout << "Dinh dang file khong hop le. Dong dau tien phai la so nguyen (so dinh)." << endl; return 1; } catch (const std::out_of_range& e) { cout << "So dinh qua lon." << endl; return 1; } } else { cout << "File trong hoac khong doc duoc dong dau tien." << endl; return 1; } // Kiểm tra số đỉnh phải là số dương. if (n <= 0) { cout << "So dinh phai la so duong." << endl; return 1; } // Khởi tạo đồ thị dưới dạng danh sách kề: // Mỗi phần tử của vector graph là một vector chứa các cặp {đỉnh kề, trọng số (double)} vector<vector<pair<int, double>>> graph(n); int lineNum = 1; // Biến đếm số dòng (dùng để báo lỗi nếu có) // "u, v, w" với: u - đỉnh xuất phát, v - đỉnh đích, w - trọng số (số thực) while (getline(infile, line)) { lineNum++; // Tăng số đếm dòng // Bỏ qua các dòng rỗng hoặc dòng comment (dòng bắt đầu bằng '#' có thể là chú thích) if (line.empty() || line[0] == '#') { continue; } // Sử dụng lambda để xóa các khoảng trắng dư thừa ở đầu và cuối chuỗi auto trim = [&](string &s) { while (!s.empty() && isspace((unsigned char)s.front())) s.erase(s.begin()); while (!s.empty() && isspace((unsigned char)s.back())) s.pop_back(); }; trim(line); if (line.empty()) continue; // Tách chuỗi theo dấu phẩy: sử dụng stringstream và hàm getline với dấu phân cách là dấu ',' vector<string> tokens; { string token; stringstream ss(line); // Đặt locale của stringstream thành "C" để đảm bảo dấu chấm ('.') được xử lý đúng ss.imbue(locale("C")); while (getline(ss, token, ',')) { trim(token); // Loại bỏ các khoảng trắng dư thừa xung quanh token tokens.push_back(token); } } // Kiểm tra: dòng phải có đủ 3 trường (u, v, w) if (tokens.size() < 3) { cerr << "Canh bao: Dinh dang dong " << lineNum << " khong dung (can 3 truong u,v,w). Bo qua dong: \"" << line << "\"\n"; continue; } // Biến tạm để lưu giá trị của u, v, và w sau khi chuyển đổi int u, v; double w; try { u = stoi(tokens[0]); // Chuyển token đầu tiên thành số nguyên (đỉnh u) v = stoi(tokens[1]); // Chuyển token thứ hai thành số nguyên (đỉnh v) w = stod(tokens[2]); // Chuyển token thứ ba thành số thực (trọng số w) } catch (...) { cerr << "Canh bao: Khong the chuyen doi u,v,w o dong " << lineNum << ". Bo qua dong.\n"; continue; } // Kiểm tra tính hợp lệ của chỉ số đỉnh: phải nằm trong khoảng [0, n-1] if (u < 0 || u >= n || v < 0 || v >= n) { cerr << "Canh bao: Dinh khong hop le o dong " << lineNum << " (u=" << u << ", v=" << v << "). Dinh phai trong khoang [0, " << n-1 << "]. Bo qua canh nay.\n"; continue; } // Cảnh báo nếu trọng số âm (chú ý: Dijkstra không đảm bảo đúng với trọng số âm) if (w < 0) { cerr << "Canh bao: Trong so am o dong " << lineNum << " (w=" << w << "). Dijkstra co the cho ket qua sai. Dang tiep tuc xu ly...\n"; } // Thêm cạnh vào đồ thị. // Trong ví dụ này, đồ thị được coi là có hướng: thêm cạnh từ đỉnh u đến đỉnh v với trọng số w. graph[u].push_back({v, w}); // Nếu đồ thị là vô hướng, bạn có thể mở comment dòng sau: // graph[v].push_back({u, w}); } // ***** HẾT PHẦN THAY ĐỔI ĐỌC DỮ LIỆU ***** // Đóng file sau khi đọc xong infile.close(); // ---- Nhập đỉnh bắt đầu và đỉnh kết thúc để tính đường đi --- int start = -1, end = -1; cout << "\nNhap dinh bat dau (0-" << n - 1 << "): "; // Lặp cho đến khi người dùng nhập đúng định dạng và nằm trong khoảng cho phép. while (!(cin >> start) || start < 0 || start >= n) { cout << "Dinh bat dau khong hop le. Vui long nhap lai (0-" << n - 1 << "): "; cin.clear(); cin.ignore(numeric_limits<streamsize>::max(), '\n'); } // Yêu cầu nhập đỉnh kết thúc. // Người dùng có thể nhập số hay ký hiệu '#' (mặc định đặt đỉnh kết thúc là đỉnh cuối cùng n-1) cout << "Nhap dinh ket thuc (0-" << n - 1 << ", nhap '#' de su dung dinh " << n - 1 << "): "; string destInput; while(true) { cin >> destInput; if (destInput == "#") { end = n - 1; break; } else { try { end = stoi(destInput); if (end >= 0 && end < n) { break; } else { cout << "Dinh ket thuc ngoai pham vi. Vui long nhap lai (0-" << n - 1 << " hoac '#'): "; } } catch (...) { cout << "Dau vao khong hop le. Vui long nhap lai (0-" << n - 1 << " hoac '#'): "; cin.clear(); cin.ignore(numeric_limits<streamsize>::max(), '\n'); } } } // Hỏi người dùng có muốn hiển thị thời gian thực hiện của thuật toán Dijkstra hay không. // cout << "Ban co muon kiem tra hieu suat thuat toan khong? (y/n): "; //char perfChoice; //cin >> perfChoice; //bool checkPerf = (perfChoice == 'y' || perfChoice == 'Y'); // ---- Thực hiện thuật toán Dijkstra và đo thời gian ---- vector<double> dist; // Vector lưu khoảng cách ngắn nhất từ đỉnh start đến các đỉnh khác vector<int> prev; // Vector lưu đường đi (đỉnh đi trước của mỗi đỉnh) // Lấy thời điểm bắt đầu thực hiện thuật toán auto startTime = chrono::high_resolution_clock::now(); dijkstra(graph, start, dist, prev); // Lấy thời điểm kết thúc thực hiện thuật toán auto endTime = chrono::high_resolution_clock::now(); // Tính thời gian thực hiện tính theo milli giây double duration = chrono::duration<double, milli>(endTime - startTime).count(); // Nếu người dùng chọn hiển thị thời gian, in ra kết quả. // if (checkPerf) { // cout << "Thoi gian thuc hien thuat toan: " // << fixed << setprecision(4) << duration << " ms" << endl; // } // ---- In kết quả đường đi ---- // Kiểm tra nếu không tìm thấy đường đi từ đỉnh start đến end. if (dist[end] >= numeric_limits<double>::max() - 1.0) { cout << "\nKhong tim thay duong di tu dinh " << start << " den dinh " << end << "." << endl; } else { // Nếu tìm thấy, tái tạo đường đi bằng cách duyệt ngược vector prev. vector<int> path = reconstruct_path(start, end, prev); if (path.empty()) { cout << "\nKhong the tai tao duong di tu dinh " << start << " den dinh " << end << " (co the dinh ket thuc khong toi duoc hoac loi logic)." << endl; } else { // In ra đường đi ngắn nhất tìm được: cout << "\nDuong di ngan nhat tu dinh " << start << " den dinh " << end << ":" << endl; for (size_t i = 0; i < path.size(); ++i) { cout << path[i]; if (i < path.size() - 1) { cout << " -> "; } } // In tổng khoảng cách của đường đi đó với định dạng số thực (2 chữ số sau dấu phẩy) cout << "\n\nTong khoang cach: " << fixed << setprecision(2) << dist[end] << endl; } } std::cout << "\n"; return 0; // Kết thúc chương trình thành công. }
Editor is loading...
Leave a Comment