Complexity Of Dijkstra's algorithm

问题:

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.

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;
    }
}

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.

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:

1. How is Dijkstra's algo O(VLogV) especially given the above counterexample?
2. How could I optimise my code so that it could achieve O(VLogV) complexity (or better)?

Edit:

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).

回答1:

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):

• Insert
• Update
• Find/Delete minimum

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.

• Originally Dijkstra implemented the Frontier set using an unsorted array. Thus it was O(1) for Insert and Update, but O(|V|) for Find/Delete minimum, resulting in O(|E| + |V|^2), but since |E| < |V|^2, you have O(|V|^2).

• 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|).

• 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.

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.

回答2:

Improving Dijkstra by using a BST or heap will lead to time complexities like O(|E|log|V|) or O(|E|+|V|log|V|), see Dijkstra's running time. Each edge has to be checked at some point.