I found the introduction of dijkstra algorithm in geeksforgeeks: https://www.geeksforgeeks.org/introduction-to-dijkstras-shortest-path-algorithm/
time complexity of dijkstra algorithm
Pseudocode:
function Dijkstra(Graph, source):
// Initialize distances to all nodes as infinity, except for the source node.
distances = map infinity to all nodes
distances = 0
// Initialize an empty set of visited nodes and a priority queue to keep track of the nodes to visit.
visited = empty set
queue = new PriorityQueue()
queue.enqueue(source, 0)
// Loop until all nodes have been visited.
while queue is not empty:
// Dequeue the node with the smallest distance from the priority queue.
current = queue.dequeue()
// If the node has already been visited, skip it.
if current in visited:
continue
// Mark the node as visited.
visited.add(current)
// Check all neighboring nodes to see if their distances need to be updated.
for neighbor in Graph.neighbors(current):
// Calculate the tentative distance to the neighbor through the current node.
tentative_distance = distances[current] + Graph.distance(current, neighbor)
// If the tentative distance is smaller than the current distance to the neighbor, update the distance.
if tentative_distance < distances[neighbor]:
distances[neighbor] = tentative_distance
// Enqueue the neighbor with its new distance to be considered for visitation in the future.
queue.enqueue(neighbor, distances[neighbor])
// Return the calculated distances from the source to all other nodes in the graph.
return distances
It indicates that the worst case time complexity is O((V + E) log V), what is the time complexity of best case scenario?
I search through the internet and found nothing about the time complexity for best case