Dijkstra算法的复杂度 [英] Complexity Of Dijkstra's algorithm
问题描述
我从许多消息来源获悉，如果使用天真的方法来获取最小元素（线性搜索），则迪杰斯特拉的最短路径也将以O（V ^ 2）复杂度运行。但是，如果使用优先级队列，则可以将其优化为O（VLogV），因为此数据结构将在O（1）时间返回min元素，但是在删除min元素后需要O（LogV）时间来恢复堆属性。
I read from many sources that Dijkstra's Shortest Path also will run in O(V^2) complexity if using a naive way to get the min element (linear search). However, it can be optimised to O(VLogV) if priority queue is used as this data structure will return min element in O(1) time but takes O(LogV) time to restore the heap property after deleting the min element.
我在以下链接中针对UVA问题的以下代码中实现了Dijkstra的算法： https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=16& ; page = show_problem& problem = 1927 ：
I have implemented Dijkstra's algo in the following code for the UVA problem at this link: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=16&page=show_problem&problem=1927:
#include<iostream>
#include<vector>
#include <climits>
#include <cmath>
#include <set>
using namespace std;
#define rep(a,b,c) for(int c=a;c<b;c++)
typedef std::vector<int> VI;
typedef std::vector<VI> VVI;
struct cmp {
bool operator()(const pair<int,int> &a,const pair<int,int> &b) const {
return a.second < b.second;
}
};
void sp(VVI &graph,set<pair<int,int>,cmp> &minv,VI &ans,int S,int T) {
int e = -1;
minv.insert(pair<int,int>(S,0));
rep(0,graph.size() && !minv.empty() && minv.begin()->first != T,s) {
e = minv.begin()->first;
minv.erase(minv.begin());
int nb = 0;
rep(0,graph[e].size(),d) {
nb = d;
if(graph[e][d] != INT_MAX && ans[e] + graph[e][d] < ans[d]) {
set<pair<int,int>,cmp>::iterator si = minv.find(pair<int,int>(d,ans[d]));
if(si != minv.end())
minv.erase(*si);
ans[d] = ans[e] + graph[e][d];
minv.insert(pair<int,int>(d,ans[d]));
}
}
}
}
int main(void) {
int cc = 0,N = 0,M = 0,S = -1,T = -1,A=-1,B=-1,W=-1;
VVI graph;
VI ans;
set<pair<int,int>,cmp> minv;
cin >> cc;
rep(0,cc,i) {
cin >> N >> M >> S >> T;
graph.clear();
ans.clear();
graph.assign(N,VI());
ans.assign(graph.size(),INT_MAX);
minv.clear();
rep(0,N,j) {
graph[j].assign(N,INT_MAX);
}
ans[S] = 0;
graph[S][S] = 0;
rep(0,M,j) {
cin >> A >> B >> W;
graph[A][B] = min(W,graph[A][B]);
graph[B][A] = min(W,graph[B][A]);
}
sp(graph,minv,ans,S,T);
cout << "Case #" << i + 1 << ": ";
if(ans[T] != INT_MAX)
cout << ans[T] << endl;
else
cout << "unreachable" << endl;
}
}
根据我的分析，我的算法具有O（ VLogV）的复杂性。 STL std :: set被实现为二进制搜索树。此外，该集合也被排序。
因此从中获得的最小元素为O（1），插入和删除的每个元素均为O（LogV）。但是，我仍然可以从这个问题中获得一个TLE，根据给定的时间限制，该问题应该可以在O（VLogV）中解决。
Based on my analysis, my algorithm has a O(VLogV) complexity. The STL std::set is implemented as a binary search tree. Furthermore, the set is sorted too. Hence getting the minimum element from it is O(1), insertion and deletion is O(LogV) each. However, I am still getting a TLE from this problem which should be solvable in O(VLogV) based on the given time limit.
这使我进行了更深入的思考。如果所有节点都互连在一起，以使每个顶点V具有V-1邻居，该怎么办？
This led me to think deeper. What if all nodes were interconnected such that each vertex V has V-1 neighbours? Won't it make Dijkstra's algorithm run in O(V^2) since each vertex has to look at V-1,V-2,V-3... nodes every round?
再三考虑，我可能误解了最坏情况的复杂性。有人可以在以下问题上为我提供建议吗？
On second thoughts, I might have misinterpreted the worst case complexity. Could someone please advise me on the following issues:
- 尤其是在上述反例的情况下，Dijkstra的算法O（VLogV）怎么样？
- 如何优化代码以使其达到O（VLogV）复杂度（或更优）？
编辑：
我意识到我的程序毕竟不能在O（ElogV）中运行。瓶颈是由我在O（V ^ 2）中运行的输入处理引起的。 dijkstra部分确实在（ElogV）中运行。
I realised that my program does not run in O(ElogV) after all. The bottleneck is caused by my input processing which runs in O(V^2). The dijkstra part indeed runs in (ElogV).
推荐答案
为了理解Dijkstra算法的时间复杂性，我们需要研究在用于实现Frontier集的数据结构上执行的操作（即算法中用于 minv 的数据结构）：
In order to understand the time complexity of Dijkstra's algorithm, we need to study the operations that are performed on the data structure that is used to implement the Frontier set (i.e. the data structure used for minv in your algorithm):
- 插入
- 更新
- 查找/删除最小值
有 O（| V |）插入， O（| E | ）更新， O（| V |）查找/删除算法整个持续时间内数据结构上出现的最小值。
There are O(|V|) inserts, O(|E|) updates, O(|V|) Find/Delete Minimums in total that occur on the data structure for the entire duration of the algorithm.
-
最初Dijkstra使用未排序的数组实现了Frontier集。因此，对于插入和更新，它为
O（1），但对于查找/删除最小值为O（| V |），导致O（| E | + | V | ^ 2），但由于| E | < | V | ^ 2，您有O（| V | ^ 2）。
Originally Dijkstra implemented the Frontier set using an unsorted array. Thus it was
O(1)for Insert and Update, butO(|V|)for Find/Delete minimum, resulting inO(|E| + |V|^2), but since|E| < |V|^2, you haveO(|V|^2).
如果使用二进制min-heap来实现Frontier集，则所有操作都具有 log（| v |），导致 O（| E | log | V | + | V | log | V |），但是由于假定 | E |是合理的> | V | ，您有 O（| E | log | V |）。
If a binary min-heap is used to implement the Frontier set, you have log(|v|) for all operations, resulting in O(|E|log|V| + |V|log|V|), but since it is reasonable to assume |E| > |V|, you have O(|E|log|V|).
然后是Fibonacci堆，您在其中的 O（1）摊销时间为最小插入/更新/查找，但 O（ log | V |）最小删除的分摊时间，为您提供当前最著名的时间范围 O（| E | + | V | log | V |）
Then came the Fibonacci heap, where you have O(1) amortized time for Insert/Update/Find minimum, but O(log|V|) amortized time for Delete minimum, giving you the currently best known time bound of O(|E| + |V|log|V|) for Dijkstra's algorithm.
最后，是一种解决<$中单源最短路径问题的算法c $ c> O（| V | log | V |）如果（| V | log | V |< | E |），因为问题的下限很短， O（| E | + | V |），即您需要检查每个顶点和边至少可以解决一次。
Finally, an algorithm for solving the Single Source Shortest Paths problem in O(|V|log|V|) worst case time complexity is not possible if (|V|log|V| < |E|), since the problem has the trivial lower time bound of O(|E| + |V|) i.e. you need to inspect each vertex and edge at least once to solve the problem.
这篇关于Dijkstra算法的复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
