Dijkstra's algorithm is a pathfinding algorithm used to find the shortest path between two nodes in a weighted graph. The algorithm works by maintaining a set of visited nodes and a set of unvisited nodes. Initially, the distance to the starting node is set to 0, and the distance to all other nodes is set to infinity.
1. Start by selecting the starting node and setting its distance to 0.
2. Visit the neighbors of the starting node and update their distances if they are shorter than the current distance.
3. Mark the starting node as visited and select the unvisited node with the shortest distance as the current node.
4. Visit the neighbors of the current node and update their distances if they are shorter than the current distance.
5. Mark the current node as visited and select the unvisited node with the shortest distance as the new current node.
6. Repeat steps 4-5 until the destination node is marked as visited or there are no more unvisited nodes.
7. Once the destination node is marked as visited, the algorithm has found the shortest path. The path can be traced back from the destination node to the starting node by following the parent nodes that were recorded during the algorithm.
Note: Dijkstra's algorithm only works with non-negative edge weights.
No comments:
Post a Comment