Đồ thị (Graph) Phần 5: Các thuật toán tìm đường đi ngắn nhất trên đồ thị có trọng số (Phần 1) – Dijkstra

6 9 1 6
1 3 2
1 4 3
1 5 6
4 5 7
4 6 2
1 2 1
3 2 4
2 5 3
6 3 10

5
1 4 6

	#define pii pair<int, int>
	priority_queue<pii, vector<pii>, greater<pii>> q;
	// các phần tử của priority_queue sẽ được lưu dưới dạng pair {d[v], v} 
        // và được tự động sort theo chiều tăng dần của d[v]. 

        if (d[x] > d[v] + c) {
	    d[x] = d[v] + c;
	    pq.push(make_pair(d[v], v));
        }

// quy ước:
// push(d[x], x): cho (d[x], x) vào priority_queue
// top(): phần tử đầu tiên của priority_queue
// pop(): xóa phần tử đầu tiên ở priority_queue

void dijkstra(s):
   gán tất cả giá trị d[u] là +∞
   d[s] = 0
   // coi khoảng cách từ s tới chính nó là 0
   push(d[s], s)
   trong khi priority_queue chưa rỗng:
	u = front().second
	c = front().first
	// xét đỉnh có d[u] nhỏ nhất trong priority_queue
	pop()
	if (c > d[u]) bỏ qua
	// nếu như đỉnh u đã cố định thì bỏ qua
	for v kề u:
		if (d[v] > d[u] + c):
			d[v] = d[u] + c
			push(d[v], v)

#include<bits/stdc++.h>
using namespace std;

#define pii pair<int, int>
#define inf 1e18
#define int long long

const int N = 1e5 + 2;

int n, m, S, T;
vector<pii> adj[N];
int trace[N], d[N];

void dijkstra() {
	for (int i = 1; i <= n; i++) {
    	    d[i] = inf;
    	    // gán toàn bộ mảng d có giá trị là +∞
	}
	d[S] = 0;
	// gán đỉnh bắt đầu là 0
	priority_queue<pii, vector<pii>, greater<pii>> q;
	// các phần tử của priority_queue sẽ được lưu dưới dạng pair {d[v], v}
	// và được tự động sort theo chiều giảm dần của d[v].
	q.push({d[S], S});
	// đẩy đỉnh ban đầu và quãng đường tới chính nó vào priority_queue
	while (q.size()) {
    	      // khi priority_queue chưa rỗng
    	      int c = q.top().first;
    	      int u = q.top().second;
    	      q.pop();
    	      // xét đỉnh có d[u] nhỏ nhất trong priority_queue
    	      if (c > d[u]) {
        	 continue;
        	// nếu d[u] đã được cố định -> bỏ qua đỉnh này
    	      } 
    	      for (auto v : adj[u]) {
        	   if (d[v.first] > d[u] + v.second) {
            	       d[v.first] = d[u] + v.second;
            	       trace[v.first] = u;
            	       q.push({d[v.first], v.first});
        	   }
    	      }
	}
	cout << d[T] << 'n';
}

void findPath() {
	vector<int> path;
	while (true) {
    	      path.push_back(T);
    	      if (T == S) {
        	 break;
    	      }
    	      T = trace[T];
        }
	for (int i = path.size() - 1; i >= 0; i--) {
    		cout << path[i] << " ";
	}
}

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr);
	cin >> n >> m >> S >> T;
	for (int i = 1; i <= m; i++) {
    	     int u, v, c; cin >> u >> v >> c;
    	     adj[u].push_back(make_pair(v, c));
    	     // đỉnh v kề u có trọng số c
    	     adj[v].push_back(make_pair(u, c));
    	     // đỉnh u kề v có trọng số c
	}
	dijkstra();
	findPath();
}

5 5
0 1 5
1 2 4
0 3 8
2 3 2
4 2 3

13

#include<bits/stdc++.h>
using namespace std;

#define pii pair<int, int>
#define inf 1e18
#define int long long

const int N = 1e5 + 2;

int n, m;
vector<pii> adj[N];
int d1[N], d2[N];

void dijkstra1() {
	for (int i = 0; i < n; i++) {
    	     d1[i] = inf;
	}
	d1[0] = 0;
	priority_queue<pii, vector<pii>, greater<pii>> q;
	q.push({d1[0], 0});
	while (q.size()) {
    	     int c = q.top().first;
    	     int u = q.top().second;
    	     q.pop();
    	     if (c > d1[u]) {
        	 continue;
    	     }
    	     for (auto v : adj[u]) {
        	  if (d1[v.first] > d1[u] + v.second) {
            	     d1[v.first] = d1[u] + v.second;
            	     q.push({d1[v.first], v.first});
        	}
    	     }
	}
}

void dijkstra2() {
	for (int i = 0; i < n; i++) {
    	    d2[i] = inf;
	}
	d2[n - 1] = 0;
	priority_queue<pii, vector<pii>, greater<pii>> q;
	q.push({d2[n - 1], n - 1});
	while (q.size()) {
    	     int c = q.top().first;
    	     int u = q.top().second;
    	     q.pop();
    	     if (c > d2[u]) {
        	continue;
    	     }
    	     for (auto v : adj[u]) {
        	  if (d2[v.first] > d2[u] + v.second) {
            	     d2[v.first] = d2[u] + v.second;
            	     q.push({d2[v.first], v.first});
        	}
    	     }
	}
}


signed main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr);
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
    	     int u, v, c; cin >> u >> v >> c;
    	     adj[u].push_back(make_pair(v, c));
    	     adj[v].push_back(make_pair(u, c));
	}
	dijkstra1();
	// tìm đường đi ngắn nhất từ 0 đến u
	dijkstra2();
	// tìm đường đi ngắn nhất từ n - 1 đến u
	int res = -inf;
	for (int i = 0; i < n; i++) {
    	     res = max(res, d1[i] + d2[i]);
	}
	cout << res;
}

#include<bits/stdc++.h>

using namespace std;

#define int long long
#define inf 1e18
#define pii pair<int, int>

const int N = 5005;

int d[N], f[N];
int n, m;
vector<pii> adj[N];

void dijkstra() {
	priority_queue<pii, vector<pii>, greater<pii>> q;
	for (int i = 1; i <= n; i++) d[i] = inf;
	d[1] = 0; f[1] = 1;
	// bài toán con
	q.push({d[1], 1});
	while (q.size()) {
		int u = q.top().second, c = q.top().first;
		q.pop();
		if (c > d[u]) 
			continue;
		for (auto v : adj[u]) {
			if (d[v.first] > d[u] + v.second) {
				d[v.first] = d[u] + v.second;
				f[v.first] = f[u];
				q.push({d[v.first], v.first});
			}
			else if (d[v.first] == d[u] + v.second) {
				d[v.first] = d[u] + v.second;
				f[v.first] += f[u];
			}
		}
	}
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int k, u, v, l; cin >> k >> u >> v >> l;
		if (k == 1) {
			adj[u].push_back({v, l});
			// tồn tại đường đi 1 chiều từ u tới v có độ dài l
		}
		else {
			adj[u].push_back({v, l});
			adj[v].push_back({u, l});
			// tồn tại đường đi 2 chiều từ u tới v
		}
	}
	dijkstra();
	cout << d[n] << " " << f[n];
	return 0;
}