Dijkstra's Pathfinding Algorithm
Performance
Time Complexity:
O(|V|2)
Space Complexity:
O(|V|)
Search Countours:
Uniform
What are Search contours?
Pathfinding Stats
Status
Running...
Visited Node Count:
0
Path Length:
N/A
Grid size: 20 x 20, Walls: 0
⚠️ Note: this animated visualization is a work-in-progress. If you are encountering errors or want to replay the animation, please refresh the page.
If you would like to report a bug or suggest an improvement, please create an issue on GitHub.
Understanding Dijkstra's Algorithm
Arguably one of the most popular pathfinding algorithms, Dijkstra's algorithm is a weighted algorithm that finds the shortest path between two nodes in a graph. While it visits all nodes in the graph, it guaranteed to find the shortest path.
To understand how Dijkstra's algorithm works, we must first understand the concept of a weighted graph. A weighted graph is a graph where each edge has a weight or cost associated with it. For example, in the graph below, the edge between node A and B has a weight of 2, while the edge between node B and C has a weight of 3. The weight of an edge represents the cost of traversing that edge. In the context of pathfinding, the weight of an edge represents the distance between two nodes. For example, if we were to represent a graph as a map, the weight of an edge would represent the distance between two cities.
Now that we understand what a weighted graph is, we can begin to understand how Dijkstra's algorithm works. Dijkstra's algorithm works by visiting each node in the graph and calculating the shortest distance from the starting node to that node. It does this by keeping track of the shortest distance from the starting node to each node in the graph. Initially, the shortest distance from the starting node to all other nodes is set to infinity. Then, the algorithm begins to visit each node in the graph. For each node, the algorithm checks each of its neighbors and calculates the distance from the starting node to that neighbor. If the calculated distance is less than the current shortest distance, the shortest distance is updated to the calculated distance. This process is repeated until all nodes in the graph have been visited.
Code Implementation
Dijkstra's pathfinding algorithm can be implemented in a variety of languages. Below are some examples of implementations in Python, C++, Go, and Java.
Note: these implementations are for educational purposes only, such as preparing for a technical interview or for learning about sorting algorithms. They are not intended to be used in production as-is, as they may not be optimized.