資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究在 C++ 中查詢任意一對不同良節點之間的最短距離
假設我們有一個給定的帶權無向圖，它有 N 個不同的節點和 M 條邊，其中一些節點是良節點。我們必須找到任意一對不同良節點之間的最短距離。在下圖中，黃色節點被認為是良節點。
因此，如果輸入類似於
那麼輸出將是 11，因為良節點對及其之間的距離為：(1 到 3) 距離為 11，(3 到 5) 距離為 13，(1 到 5) 距離為 24，其中 11 是最小值。
為了解決這個問題，我們將遵循以下步驟：
N := 100005
MAX_VAL := 99999999
建立一個優先佇列 q
result := MAX_VAL
初始化 i := 1，當 i <= n 時，更新 (i 加 1)，執行以下操作：
如果 good_verts[i] 為假，則：
忽略以下部分，跳到下一個迭代
初始化 j := 1，當 j <= n 時，更新 (j 加 1)，執行以下操作：
dist[j] := MAX_VAL
vis[j] := 0
dist[i] := 0
當 (q 不為空) 時，執行以下操作：
從 q 中刪除元素
將 { 0, i } 插入 q
good := 0
當 (q 不為空) 時，執行以下操作：
v := q 的頂部元素
從 q 中刪除元素
如果 vis[v] 為真，則：
忽略以下部分，跳到下一個迭代
vis[v] := 1
good := good + (當 good_verts[v] 為真時為 1，否則為 0)
如果 dist[v] > result，則：
退出迴圈
如果 good 等於 2 且 good_verts[v] 為真，則：
result := result 和 dist[v] 的最小值
退出迴圈
初始化 j := 0，當 j < graph[v] 的大小時，更新 (j 加 1)，執行以下操作：
to := graph[v, j].first
weight := graph[v, j].second
如果 dist[v] + weight < dist[to]，則：
dist[to] := dist[v] + weight
將 { dist[to], to } 插入 q
返回 result
示例
讓我們看看以下實現以更好地理解：
#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);
}輸入
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;
輸出
7
402 次瀏覽
