下面是我从维基百科文章中的伪代码编写的Dijkstra算法的实现.对于具有大约40 000个节点和80 000个边缘的图形,运行需要3或4分钟.那是不是正确的数量级？如果没有,我的实施有什么问题？
struct DijkstraVertex {
int index;
vector<int> adj;
vector<double> weights;
double dist;
int prev;
bool opt;
DijkstraVertex(int vertexIndex, vector<int> adjacentVertices, vector<double> edgeWeights) {
index = vertexIndex;
adj = adjacentVertices;
weights = edgeWeights;
dist = numeric_limits<double>::infinity();
prev = -1; // "undefined" node
opt = false; // unoptimized node
}
};
void dijsktra(vector<DijkstraVertex*> graph, int source, vector<double> &dist, vector<int> &prev) {
vector<DijkstraVertex*> Q(G); // set of unoptimized nodes
G[source]->dist = 0;
while (!Q.empty()) {
sort(Q.begin(), Q.end(), dijkstraDistComp); // …我的任务是(课程作业@大学)实施一种寻路方式.现在,在规范中,我可以实现一个蛮力,因为搜索节点的数量有限(开始,中间两个,结束),但我想重新使用这个代码来实现Dijkstra的算法.
我已经在维基百科上看过伪,一位朋友也为我写了一些,但它没有意义.这个算法看起来非常简单,对我来说理解它并不是一个问题,但我不能为我的生活可视化实现这种事情的代码.
有什么建议/提示吗？
编辑一些混淆:
是的,有一个目标节点和一个源节点.
我想在一般情况下实现Dijkstra,而不是"只有两个中间停止"的情况,因为我想在之后再次使用代码.另外,我只是写一个暴力实施.
我遇到一些麻烦的具体问题是存储次优的半成形路径,以防它们变得最佳.当我访问给定节点时,我只是看不到我将如何更新通过它的所有连接.
更多编辑:
现在完成几个答案,然后继续.
真正的编辑:我忘了提到一个严重的并发症,即任何两个顶点之间可以有不同的UINT_MAX距离.抱歉.事实上,我忘了处理这个问题的事实可能首先是该死的问题的原因,尽管解决方案:对我来说,选择最短的问题是显而易见的.难怪其他人对于距离变量的伪没有考虑到我的可变距离.