使用 C++ STL 实现 Dijkstra 算法

Question

我已经实现了如下的Dijkstra算法

#include <iostream>
#include <bits/stdc++.h>
#include<cstdio>
#define ll long long int
#define mod 1000000007
#define pi 3.141592653589793
#define f first
#define s second
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define vfor(e, a) for (vector<ll> :: iterator e = a.begin(); e != a.end(); e++)
#define vfind(a, e) find(a.begin(), a.end(), e)
#define forr(i, n) for (ll i = 0; i < n; i++)
#define rfor(i, n) for (ll i = n - 1; i >= 0; i--)
#define fors(i, b, e, steps) for(ll i = b; i < e; i += steps)
#define rfors(i, e, b, steps) for(ll i = e; i > b; i -= steps)
#define mp make_pair
using namespace std;

void up(pair<ll, ll> a[], ll n, ll i, ll indArray[]) {
ll ind = (i - 1) / 2;
while (ind >= 0 && a[ind].s > a[i].s) {
swap(a[ind], a[i]);
indArray[a[ind].f] = ind;
indArray[a[i].f] = i;
i = ind;
ind = (i - 1) / 2;
}
}
void down(pair<ll, ll> a[], ll n, ll i, ll indArray[]) {
ll left = 2 * i + 1;
ll right = 2 * i + 2;
ll m = a[i].s;
ll ind = i;
if (left < n && a[left].s < m) {
ind = left;
m = a[left].s;
}
if (right < n && a[right].s < m) {
ind = right;
}
if (ind != i) {
swap(a[i], a[ind]);
indArray[a[i].f] = i;
indArray[a[ind].f] = ind;
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
//    cout << setprecision(10);

ll n, m;
cin >> n >> m;
vector<pair<ll, ll>> a[n];
forr(i, m) {
ll u, v, w;
cin >> u >> v >> w;
a[u].pb(mp(v, w));
a[v].pb(mp(u, w));
}
ll parent[n];
parent[0] = -1;
pair<ll, ll> dist[n];
forr(i, n) {
dist[i] = mp(i, INT_MAX);
}
dist[0].s = 0;
ll ind[n];
iota(ind, ind + n, 0);
ll ans[n];
ans[0] = 0;
bool visited[n];
fill(visited, visited + n, false);
ll size = n;
forr(i, n) {
ll u = dist[0].f;
visited[u] = true;
ll d1 = dist[0].s;
ans[u] = dist[0].s;
swap(dist[0], dist[size - 1]);
size--;
down(dist, size, 0, ind);
for (auto e : a[u]) {
if (visited[e.f]){
continue;
}
ll v = e.f;
ll j = ind[v];
if (dist[j].s > d1 + e.s) {
dist[j].s = d1 + e.s;
up(dist, size, j, ind);
parent[v] = u;
}
}
}
stack<ll> st;
forr(i, n) {
ll j = i;
while (j != -1) {
st.push(j);
j = parent[j];
}
while (!st.empty()) {
cout << st.top() << "->";
st.pop();
}
cout << "   Path length is " << ans[i];
cout << 'n';
}
}

这个实现是正确的，并且给出了正确的输出。

可以看出，每次我选择键值最低的节点(与源的距离)，然后更新所选节点的所有相邻节点上的键。在更新了相邻节点的键之后，我将调用"up"函数来维护最小堆属性。但是优先级队列存在于c++stl中。如何使用它们来避免上下功能。

问题是，我需要能够在需要更新其密钥的平均堆中找到节点密钥对的索引。在这段代码中，我使用了一个单独的ind数组，它在每次更新最小堆时都会更新。但是如何利用c++stl

Answer 1

正如您所暗示的，我们无法使用std::priority_queue进行有效的随机访问。对于这种情况，我建议您使用std::set。它实际上不是一个堆，而是一个平衡的二进制搜索树。然而，它以您想要的方式工作。find、insert和erase方法都是O(log n)，因此您可以在所需时间内插入/擦除/更新值，因为更新可以先擦除后插入。接入最小值为O(1)。

您可以像我提到的那样引用这个参考实现。对于邻接列表，时间复杂度为O(E log V)，其中E是边的数量，V是顶点的数量。

请注意

• 使用默认比较器，如果std::set::begin()方法不为空，则返回min元素
• 在这个代码中，它把距离放在第一位，把索引放在第二位。通过这样做，集合元素按距离升序排序

%我没有详细研究您代码的up和down的实现。