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

How to use the Dijkstra Visualizer

  1. Click on empty space to create vertices.
  2. Click on one vertex and then another to create an edge.
  3. Enter the edge weight when prompted.
  4. Drag vertices to reposition them.
  5. Press Start to generate Dijkstra steps (source = v0).
  6. Use Next to go step-by-step or Run to auto-execute.

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)