Dijkstra's Algorithm

How Dijkstra's Algorithm Works

1. Initialize

Set the distance to the start node as 0 and all others as Infinity. Add all nodes to the unvisited set.

💡 Pro Tip: All nodes are unvisited. The start node has distance 0.

2. Visit Closest Node

Pick the unvisited node with the smallest distance. Mark it as visited.

💡 Pro Tip: The node with the smallest distance is chosen next.

3. Update Neighbors

For each unvisited neighbor, update its distance if a shorter path is found.

💡 Pro Tip: Neighbors get updated if a better path is found.

4. Repeat

Continue until the end node is visited or all nodes are processed.

💡 Pro Tip: The process repeats until the shortest path is found or no path exists.

5. Reconstruct Path

Trace back from the end node to the start node to get the shortest path.

💡 Pro Tip: The shortest path is highlighted.

Key Concepts

Distance

The shortest known distance from the start node to each node.

Unvisited Set

All nodes start unvisited and are removed as they are processed.

Optimality

Dijkstra's algorithm is guaranteed to find the shortest path in graphs with non-negative weights. "Priority queue" is used to always expand the lowest-cost node.

Legend

Start Node

Click and drag to move

End Node

Click and drag to move

Wall

Click to add/remove

Visited Nodes

Shortest Path

How to Use

1. Create Your Maze

Click or drag on the grid to add or remove walls

2. Position Start & End

Drag the green and red nodes to set start and end points

3. Visualize

Click "Visualize Dijkstra" to find the shortest path

4. Experiment

Try different mazes and see how Dijkstra finds the path

About Dijkstra

Dijkstra's algorithm finds the shortest path between two points in a graph with non-negative weights.

âš¡

Optimal

Always finds the shortest path

🧠

Systematic

Explores all possible paths efficiently

🎯

Versatile

Works on any graph with non-negative weights