Dijkstra's Algorithm

Dijkstra's algorithm finds the shortest path from a source vertex to all other vertices in a weighted graph with non-negative edge weights. It uses a priority queue and is widely used in routing and network protocols.

Dijkstra's Algorithm Visualization

Complexity

Time Complexity: O((V + E) log V)

Space Complexity: O(V)

Pseudocode

function Dijkstra(graph, start):
  dist = {v: ∞ for all v}
  dist[start] = 0
  pq = priority queue with (0, start)
  
  while pq is not empty:
    current = pq.extract_min()
    
    for each neighbor with weight w:
      new_dist = dist[current] + w
      if new_dist < dist[neighbor]:
        dist[neighbor] = new_dist
        pq.insert(new_dist, neighbor)

Related Algorithms

Breadth-First Search

Breadth-First Search (BFS) is a graph traversal algorithm that explores all vertices at the current depth level before moving to vertices at the next depth level. It uses a queue data structure and is useful for finding shortest paths in unweighted graphs.

Time: O(V + E) | Space: O(V)

A* Algorithm

A* is an informed search algorithm that finds the shortest path using both the actual distance from the start and an estimated distance to the goal (heuristic). It's optimal and efficient for pathfinding in games and robotics.

Time: O(b^d) | Space: O(b^d)