Dijkstra c++ 98
Sat Sep 07 2024 03:44:36 GMT+0000 (Coordinated Universal Time)
Saved by
@LizzyTheCatto
#include <iostream>
#include <vector>
#include <queue>
#include <utility> // cho std::pair
using namespace std;
void D(int N, vector<vector<pair<int, int>>> &adj, int source) {
vector<int> dist(N, 1000000); // Khởi tạo khoảng cách đến tất cả các đỉnh là vô cùng
dist[source] = 0; // Khoảng cách từ đỉnh nguồn đến chính nó là 0
// Hàng đợi ưu tiên với hàm so sánh
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int> > > pq;
pq.push(make_pair(0, source));
while (!pq.empty()) { // Trong khi hàng đợi không rỗng
int u = pq.top().second; // Lấy đỉnh có khoảng cách nhỏ nhất
int d = pq.top().first; // Khoảng cách từ nguồn đến đỉnh u
pq.pop();
// Duyệt các đỉnh kề của đỉnh u
for (int i = 0; i < adj[u].size(); i++) {
int v = adj[u][i].first; // Đỉnh kề
int weight = adj[u][i].second; // Trọng số của cạnh
// Nếu tìm được đường đi ngắn hơn đến đỉnh v
if (dist[v] > dist[u] + weight) {
dist[v] = dist[u] + weight;
pq.push(make_pair(dist[v], v)); // Đẩy khoảng cách mới vào hàng đợi
}
}
}
// In ra kết quả khoảng cách từ đỉnh nguồn đến tất cả các đỉnh khác
for (int i = 0; i < N; i++) {
cout << "Khoảng cách từ " << source << " đến " << i << " là " << dist[i] << endl;
}
}
int main() {
int N, M; // Số đỉnh, số cạnh
cin >> N >> M;
vector<vector<pair<int, int> > > adj(N); // Mảng vector để lưu đồ thị
for (int i = 0; i < M; i++) {
int a, b, c;
cin >> a >> b >> c;
adj[a].push_back(make_pair(b, c)); // Đồ thị có hướng
adj[b].push_back(make_pair(a, c)); // Nếu đồ thị là vô hướng
}
int source;
cin >> source;
D(N, adj, source);
return 0;
}
content_copyCOPY
https://www.programiz.com/cpp-programming/online-compiler/
Comments