我最近正在查看Dijkstra算法的一些代码。该代码的目标是找到从顶点1到顶点N的最小成本路径。在查看问题的解决方案时,我遇到了此工作代码:
void dijkstra(int start, int n) {
for(int i = 0; i<n; i++) {
dist[i] = INF;
pred[i] = -1;
}
dist[start] = 0;
priority_queue<ll> q;
q.push(0);
int u = 0;
while(q.size()) {
u = q.top();
q.pop();
for(int end : adj[u]) {
ll w = weight.at(mp(u, end));
if(dist[u] + w < dist[end]) {
dist[end] = dist[u] + w;
pred[end] = u;
q.push(end);
}
}
}
}
此程序使用优先级队列来确定要从下一个顶点开始遍历的顶点(从顶点1开始)。但是,用此算法实现的优先级队列是标准的C ++优先级队列,它是最大优先级队列。这意味着最大的元素具有最高的优先级。但是,我认为在Dijkstra的算法中,我们想首先轮询最小的顶点吗?我不确定对此算法使用最大优先级队列的方式。
您提到的一切都是对的。但小心点! u
是该算法中的邻居索引。而且,如果索引较高的邻居的距离更短,则它将正常工作。
此外,您应该注意,可以实施优先级队列,以便使用std::greater<T>
使顶部元素成为最小值。