Unabale to find the best case time complexity of priority queue Dijkstra Algorithm

77 views Asked by At

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

0

There are 0 answers