Dijkstra

...

1. Initialize the algorithm by setting the starting node as the current node.
2. Assign a tentative distance value of zero to the starting node and infinity to all other nodes. The tentative distance represents the shortest distance from the starting node to each node.
3. Set the current node as visited.
4. For each neighbor of the current node, calculate the tentative distance by adding the weight of the current node to the distance to the neighbor. If the tentative distance is less than the current distance assigned to the neighbor, update the neighbor's distance.
5. After considering all the neighbors, mark the current node as visited.
6. If all nodes have been visited or the smallest tentative distance among the unvisited nodes is infinity, the algorithm terminates.
7. Otherwise, select the unvisited node with the smallest tentative distance as the next current node and go back to step 4.

function Dijkstra(graph, start):
    distances := map of all nodes with infinity value
    distances[start] := 0

    visited := empty set
    unvisited := set of all nodes

    while unvisited is not empty:
        current := node in unvisited with smallest distance

        for neighbor in neighbors of current:
            tentativeDistance := distances[current] + distance(current, neighbor)
            if tentativeDistance < distances[neighbor]:
                distances[neighbor] := tentativeDistance

        visited.add(current)
        unvisited.remove(current)

    return distances
Copy

Dijkstra's algorithm starts by assigning the starting node a distance of zero and all other nodes a distance of infinity. It then iteratively selects the node with the smallest tentative distance and explores its neighbors. If the tentative distance to a neighbor through the current node is smaller than its current distance, the algorithm updates the neighbor's distance.

The algorithm continues until all nodes have been visited or the smallest tentative distance among the unvisited nodes is infinity. At the end of the algorithm, the distances map holds the shortest distances from the starting node to all other nodes in the graph.

Dijkstra's algorithm is commonly used in applications such as route planning, network routing, and traffic flow analysis. It provides an efficient way to find the shortest path in graphs with non-negative edge weights.

The time complexity of Dijkstra's algorithm depends on the data structure used for the priority queue and the graph representation.
In the commonly used implementation with a binary heap or Fibonacci heap and an adjacency list representation, the time complexity can be analyzed as follows:

• Building the priority queue takes time, where V is the number of vertices in the graph.
• For each vertex, the algorithm performs relaxation on its outgoing edges, which takes time in total, where E is the number of edges in the graph.
• Overall, the time complexity of Dijkstra's algorithm is .

However, if a simple array is used as the priority queue, the time complexity can be , as finding the vertex with the smallest distance would take time for each vertex. Therefore, using a more efficient priority queue implementation is crucial for achieving a better time complexity.

It's important to note that if the graph has a dense structure, where E is close to , the time complexity can be approximated as .

On the other hand, if the graph is sparse, with much smaller than , the time complexity is closer to .

In summary, Dijkstra's algorithm has a time complexity of or , depending on the implementation and the graph structure.