Thuật Toán Dijkstra - Đường Đi Ngắn Nhất Trên Đồ Thị

THUẬT TOÁN DIJKSTRA

Cho một đồ thị vô hướng liên thông, thuật toán Dijkstra sẽ giúp bạn tìm ra đường đi ngắn nhất từ một đỉnh bất kì đến các đỉnh còn lại.

Thuật Toán Dijkstra - Đường Đi Ngắn Nhất Trên Đồ Thị

THUẬT TOÁN

MÔ TẢ THUẬT TOÁN:

• Bước khởi tạo: Chọn một đỉnh làm đỉnh xuất phát sau đó tính khoảng cách từ đỉnh ban đầu đến các đỉnh còn lại. ( Nếu không có cạnh nào nối 2 đỉnh thì cho bằng vô cùng)
• Bước 1: Lấy đỉnh có đường đi ngắn nhất đã tính ở trên rồi đánh dấu đỉnh đó đã tìm được đường đi ngắn nhất.
• Bước 2: Từ đỉnh đó tính đường đi đến các đỉnh còn lại. Nếu tại 1 đỉnh phát hiện đường đi ngắn hơn đường đi tìm được ở bước trên thì cập nhật lại đường đi
• Lặp lại bước 2, 3 đến khi tìm được đường đi ngắn nhất tới tất cả các đỉnh.
• In ra đường  đi ngắn nhất đến tất cả các đỉnh
• Ngôn ngữ: C++

ĐỒ THỊ MẪU:

Đồ Thị Vô Hướng Liên Thông

CODE MẪU:

	#include<iostream>
	#include<map>
	#include<stack>
	#include<vector>
	using namespace std;
	vector<int> dijkstra(const vector< vector< pair<int, int> > > &adj) {
	stack< pair<int, int> > S; // Stack lưu khoảng cách ngắn nhất của mỗi bước {d[u], u}
	vector<int> d(adj.size(), INT_MAX); // vector lưu khoảng cách từ 1 đến các đỉnh khác trong đồ thị
	vector<bool> mark(adj.size(), 0); // đánh dấu các điểm đã được xét
	d[1] = 0;
	S.push({0, 1});
	while(!S.empty()) {
	int u = S.top().second;
	mark[u] = 1;
	S.pop();
	// Cập nhật khoảng cách cách các đỉnh kề với u
	for (auto e : adj[u]) {
	int v = e.first;
	int c = e.second;
	if (d[v] > d[u] + c) {
	d[v] = d[u] + c;
	}
	}
	// Tìm đỉnh có khoảng cách ngắn nhất trong các đỉnh chưa được chọn
	int d_min = INT_MAX;
	int p;
	for (int i = 0; i < adj.size(); i++) {
	if (!mark[i]) {
	if (d[i] < d_min) {
	d_min = d[i];
	p = i;
	}
	}
	}
	// Nếu có đỉnh thỏa mãn thì thêm vào Stack
	if (d_min != INT_MAX) {
	S.push({d_min, p});
	}
	}
	return d;
	}
	int main() {
	int n = 6;
	vector< vector< pair<int, int> > > adj(n + 1);
	// add khoảng cách từ u dến v
	auto add_edge = [&adj] (int u, int v, int w) {
	adj[u].push_back({v, w});
	adj[v].push_back({u, w});
	};
	add_edge(1, 3, 7);
	add_edge(1, 6, 3);
	add_edge(2, 4, 9);
	add_edge(2, 5, 6);
	add_edge(2, 6, 4);
	add_edge(3, 4, 8);
	add_edge(3, 6, 5);
	add_edge(4, 5, 2);
	add_edge(4, 6, 1);
	vector<int> distance = dijkstra(adj);
	for (unsigned int i = 1; i < distance.size(); ++i) {
	cout << "distance " << 1 << "->" << i << " = " << distance[i] << endl;
	}
	}

view raw Dijkstra.cpp hosted with ❤ by GitHub

KẾT QUẢ:

distance 1->1 = 0
distance 1->2 = 7
distance 1->3 = 7
distance 1->4 = 4
distance 1->5 = 6
distance 1->6 = 3

LỜI KẾT

Trên đây mình đã chia sẻ những hiểu biết của mình về thuật toán Dijkstra. Nếu có gì sai sót các bạn có thể để lại comment ở bên dưới để mình chỉnh sửa. Cảm ơn các bạn đã đọc bài viết !

Đánh Giá Bài Viết: