Complexity Of Dijkstra's algorithm

Question

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:

How is Dijkstra's algo O(VLogV) especially given the above counterexample?
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).

wookie919 · Accepted Answer · 2016-08-06T09:14:54.933

21

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.

edited Aug 06 '16 at 09:14

answered Aug 05 '16 at 01:33

wookie919

3,054
24
32

+1. nice answer. one question. at each step we have O|E| update in worst case? why? I means if we want say amortized cost of update can we say what? O(|E| / |N| )? – Nov 27 '20 at 04:31
@MioUnio `O(|E|)` updates in total for the whole algorithm, not at each step. – wookie919 Nov 27 '20 at 05:41
so what is the amortized cost of update of each vertex? – Nov 27 '20 at 08:37
Amortized cost is only relevant for the Fibonacci heap. For an unsorted array, each update is `O(1)`, thus `O(|E|)` for ALL updates. For a binary min-heap, each update is `O(log|V|)`, thus `O(|E|log|V|)` for ALL updates. For Fibonacci heap, worst case for a single update (decrease-key) can be up to `O(|V|)` I believe, but it can be shown that "on average" it takes `O(1)` for the duration of the algorithm, thus the amortized time of `O(1)` each update, or `O(|E|)` for all updates. – wookie919 Nov 27 '20 at 09:47
please see page 23 of this lecture https://courses.cs.washington.edu/courses/cse373/18wi/files/slides/lecture-19.pdf for unsorted array we can say O(E/V) where V is number of vertex is amortized analysis? – Nov 27 '20 at 10:02
Looks like "Hash map" in page 23 is equivalent to what I referred to as "Unsorted array" in my answer above. There is nothing in the linked slides about "Amortized analysis" and it even states that the Fibonacci Heap is out of scope. As I said above, Amortized analysis is relevant to the Fibonacci Heap, but not unsorted arrays or binary heaps. – wookie919 Nov 28 '20 at 00:16
so my last question, O(E / V) is the amortized analysis of update cost foe each vertex. where is comes? all update is O(E) in worst case? then divide by number of vertex and then multiply by O(1) time of each update? – Nov 28 '20 at 02:05
"O(E / V) is the amortized analysis of update cost foe each vertex." Where are you getting this from? I think it will be best if you ask this as a separate question. – wookie919 Nov 28 '20 at 02:10

Daniel Rodriguez · Answer 2 · 2016-08-23T11:39:54.633

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.

edited Aug 23 '16 at 11:39

answered Aug 04 '16 at 23:34

Daniel Rodriguez

607
6
11

Complexity Of Dijkstra's algorithm

2 Answers2

Linked