Giả sử chúng ta có một đồ thị vô hướng có trọng số đã cho với N nút và M cạnh khác nhau, một số nút là nút tốt. Chúng ta phải tìm khoảng cách ngắn nhất giữa bất kỳ cặp nào của hai nút tốt khác nhau. Trong sơ đồ đã cho, màu vàng trong biểu đồ sau được coi là các nút tốt.
Vì vậy, nếu đầu vào giống như
thì đầu ra sẽ là 11, vì các cặp nút tốt và khoảng cách giữa chúng là:(1 đến 3) khoảng cách là 11, (3 đến 5) khoảng cách là 13, (1 đến 5) khoảng cách là 24, hết trong đó 11 là mức tối thiểu.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
N:=100005
-
MAX_VAL:=99999999
-
tạo một hàng đợi ưu tiên q
-
kết quả:=MAX_VAL
-
để khởi tạo i:=1, khi i <=n, cập nhật (tăng i lên 1), thực hiện -
-
nếu good_verts [i] là false, thì -
-
Bỏ qua phần sau, chuyển sang phần tiếp theo
-
-
để khởi tạo j:=1, khi j <=n, cập nhật (tăng j lên 1), thực hiện -
-
dist [j]:=MAX_VAL
-
vis [j]:=0
-
-
dist [i]:=0
-
while (không phải q trống), do -
-
xóa phần tử khỏi q
-
-
chèn {0, i} vào q
-
tốt:=0
-
while (không phải q trống), do -
-
v:=phần tử hàng đầu của q
-
xóa phần tử khỏi q
-
nếu vis [v] là true, thì -
-
Bỏ qua phần sau, chuyển sang phần tiếp theo
-
-
vis [v]:=1
-
good:=good + (1 khi good_verts [v] là true, ngược lại là 0)
-
nếu dist [v]> kết quả, thì -
-
Ra khỏi vòng lặp
-
-
nếu good giống như 2 và good_verts [v], thì -
-
result:=tối thiểu của kết quả và dist [v]
-
Ra khỏi vòng lặp
-
-
để khởi tạo j:=0, khi j
-
thành:=graph [v, j] .first
-
weight:=graph [v, j] .second
-
nếu dist [v] + weight
-
dist [to]:=dist [v] + trọng lượng
-
chèn {dist [to], to} vào q
-
-
-
-
-
trả về kết quả
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#include <bits/stdc++.h>
using namespace std;
#define N 100005
#define MAX_VAL 99999999
void insert_edge(vector<pair<int, int> > graph[], int x, int y, int weight) {
graph[x].push_back({ y, weight });
graph[y].push_back({ x, weight });
}
int get_min_dist(vector<pair<int, int> > graph[], int n, int dist[], int vis[], int good_verts[], int k) {
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int>>> q;
int result = MAX_VAL;
for (int i = 1; i <= n; i++) {
if (!good_verts[i])
continue;
for (int j = 1; j <= n; j++) {
dist[j] = MAX_VAL;
vis[j] = 0;
}
dist[i] = 0;
while (!q.empty())
q.pop();
q.push({ 0, i });
int good = 0;
while (!q.empty()) {
int v = q.top().second;
q.pop();
if (vis[v])
continue;
vis[v] = 1;
good += good_verts[v];
if (dist[v] > result)
break;
if (good == 2 and good_verts[v]) {
result = min(result, dist[v]);
break;
}
for (int j = 0; j < graph[v].size(); j++) {
int to = graph[v][j].first;
int weight = graph[v][j].second;
if (dist[v] + weight < dist[to]) {
dist[to] = dist[v] + weight;
q.push({ dist[to], to });
}
}
}
}
return result;
}
int main() {
int n = 5, m = 5;
vector<pair<int, int> > graph[N];
insert_edge(graph, 1, 2, 3);
insert_edge(graph, 1, 2, 3);
insert_edge(graph, 2, 3, 4);
insert_edge(graph, 3, 4, 1);
insert_edge(graph, 4, 5, 8);
int k = 3;
int good_verts[N], vis[N], dist[N];
good_verts[1] = good_verts[3] = good_verts[5] = 1;
cout << get_min_dist(graph, n, dist, vis, good_verts, k);
} Đầu vào
n = 5, m = 5 insert_edge(graph, 1, 2, 3); insert_edge(graph, 1, 2, 3); insert_edge(graph, 2, 3, 4); insert_edge(graph, 3, 4, 1); insert_edge(graph, 4, 5, 8); k = 3 good_verts[1] = good_verts[3] = good_verts[5] = 1;
Đầu ra
7