Dijkstra’s shortest path algorithm is O(ElogV) where:
Vis the number of verticesEis the total number of edges
Your analysis is correct, but your symbols have different meanings! You say the algorithm is O(VElogV) where:
Vis the number of verticesEis the maximum number of edges attached to a single node.
Let’s rename your E to N. So one analysis says O(ElogV) and another says O(VNlogV). Both are correct and in fact E = O(VN). The difference is that ElogV is a tighter estimation.
Related Posts:
- What does O(log n) mean exactly?
- What does O(log n) mean exactly?
- Breadth First Search time complexity analysis
- O(n log n) vs O(n) — practical differences in time complexity
- Which is better: O(n log n) or O(n^2)
- Difference between Big-O and Little-O Notation
- Why is O(n) better than O( nlog(n) )?
- A tool for calculating the big-O time complexity of Java code? [closed]
- Is Dijkstra’s algorithm for directed or undirected graphs?
- How do I check if an array includes a value in JavaScript?
- Dijkstra’s algorithm in python
- how to calculate binary search complexity
- Dijkstra’s algorithm in python
- Why is the time complexity of both DFS and BFS O( V + E )
- Time complexity of a Priority Queue in C++
- Explanation of runtimes of BFS and DFS
- Counting the sum of every nodes’ neighbors’ degrees?
- Time Complexity of the Kruskal Algorithm?
- Difference and advantages between dijkstra & A star
- Example of O(n!)?
- When will the worst case of Merge Sort occur?
- Big O, how do you calculate/approximate it?
- Why doesn’t Dijkstra’s algorithm work for negative weight edges?
- How can I create an array of linked lists in java?
- Good Java graph algorithm library?
- Best case time complexity for selection sort
- Trie complexity and searching
- Is log(n!) = Θ(n·log(n))?
- Is complexity O(log(n)) equivalent to O(sqrt(n))?
- How to calculate big-theta
- What is the time complexity of while loops?
- Merge sort time and space complexity
- Why lookup in a Binary Search Tree is O(log(n))?
- How to calculate time complexity of backtracking algorithm?
- Hash table runtime complexity (insert, search and delete)
- Quickselect time complexity explained
- What’s the difference between uniform-cost search and Dijkstra’s algorithm?
- Order functions by growth rate
- Bellman-Ford vs Dijkstra: Under what circumstances is Bellman-Ford better?
- Big Oh for (n log n)
- What is the big-O of the function (log n)^k
- How do I find the time complexity (Big O) of while loop?
- Is there an O(n) integer sorting algorithm?
- Computational complexity of Fibonacci Sequence
- Which algorithm is faster O(N) or O(2N)?
- Difference between Big-Theta and Big O notation in simple language
- Time complexity of nested for-loop
- How are the following functions O(N^3)?
- Difference between O(n) and O(log(n)) – which is better and what exactly is O(log(n))?
- Are there any real O(n^n) algorithms?
- Running time of algorithm A is at least O(n²) – Why is it meaningless?
- In a triangulated isometric grid, what triangle is a given point in?
- What is tail recursion?
- What is a loop invariant?
- What is a loop invariant?
- Kadane’s algorithm explained
- Unfamiliar symbol in algorithm: what does ∀ mean? [closed]
- When is it practical to use Depth-First Search (DFS) vs Breadth-First Search (BFS)? [closed]
- Removing duplicates in lists
- what does O(N) mean [duplicate]
- How do you change the size of figures drawn with Matplotlib?
- What is Sliding Window Algorithm? Examples?
- How to generate all permutations of a list?
- Quicksort with Python
- matplotlib savefig() plots different from show()
- What is the difference between tree depth and height?
- Is it more efficient to copy a vector by reserving and copying, or by creating and swapping? [duplicate]
- how to implement quick sort algorithm in C++
- Python: maximum recursion depth exceeded while calling a Python object
- Algorithms in O(n^2) vs O(n) [duplicate]
- Python: maximum recursion depth exceeded while calling a Python object
- What is stability in sorting algorithms and why is it important?
- A proper way to create a matrix in c++
- How can you profile a Python script?
- How do you change the size of figures drawn with Matplotlib?
- Time Complexity of Prims Algorithm?
- A proper way to create a matrix in c++
- Determining complexity for recursive functions (Big O notation)
- Quick Sort Vs Merge Sort
- Polynomial time and exponential time
- Python equivalent to ‘hold on’ in Matlab
- Why does cache use Most Recently Used (MRU) algorithm as evict policy?
- Insertion Sort vs. Selection Sort
- Minimum Spanning Tree: What exactly is the Cut Property?
- Best Case for Bubble Sort
- How to find the kth smallest element in the union of two sorted arrays?
- Finding the max/min value in an array of primitives using Java
- Will Arrays.sort() increase time complexity and space time complexity?
- Performing Breadth First Search recursively
- Is Quicksort in-place or not?
- Find how many connected groups of nodes in a given adjacency matrix
- Python: maximum recursion depth exceeded while calling a Python object
- How to increase plt.title font size?
- longest increasing subsequence(O(nlogn))
- How can I create an array of linked lists in java?
- When should I use Kruskal as opposed to Prim (and vice versa)?
- Trying to understand max heapify
- Shortest possible depth of a leaf in decision tree (comparison sorting algorithm)
- Python Weighted Random [duplicate]
- What is the meaning of “exclusive” and “inclusive” when describing number ranges?