Skip to content

Instantly share code, notes, and snippets.

@jasonm23
Last active August 26, 2023 04:40
Show Gist options
  • Save jasonm23/7690782b695d22ca5000ae8be3095707 to your computer and use it in GitHub Desktop.
Save jasonm23/7690782b695d22ca5000ae8be3095707 to your computer and use it in GitHub Desktop.
Dijkstra's A* Algorithm in plain english

Dijkstra's (A*) Algorithm in plain English

Inputs: A graph or grid where each node represents a location and has associated costs, and a start node and a goal node.

Goal: Find the shortest path from the start node to the goal node while considering the associated costs and heuristics.

  1. Initialize Open and Closed Sets:

    • Create an open set containing the start node. This set represents nodes to be evaluated.
    • Create an empty closed set. This set represents nodes that have already been evaluated.
  2. Main Loop:

    • While the open set is not empty:
      • Choose the node from the open set with the lowest combined cost f(n) = g(n) + h(n), where g(n) is the cost to reach the current node and h(n) is a heuristic estimate of the cost to reach the goal.
      • If the chosen node is the goal node, the path has been found. Construct the path by following parent pointers from the goal node to the start node.
      • Move the chosen node from the open set to the closed set.
  3. Expand Node and Update Open Set:

    • For each neighboring node of the chosen node:
      • If the node is in the closed set, skip it.
      • If the node is not in the open set, add it to the open set and set its parent pointer to the chosen node.
      • If the node is already in the open set, calculate the tentative g score (cost to reach the current node). If the tentative score is lower than the existing score, update the node's parent and g score.
  4. Heuristics:

    • The choice of heuristic h(n) affects the efficiency of the A* algorithm. A good heuristic should provide an optimistic estimate of the remaining cost from the current node to the goal. Common heuristics include Euclidean distance, Manhattan distance, and octile distance.
  5. Result:

    • If the open set becomes empty and the goal node is not reached, no path exists from the start node to the goal node.

Advantages:

  • A* is guaranteed to find the shortest path if the heuristic is admissible (never overestimates the true cost) and consistent (satisfies the triangle inequality).
  • The use of heuristics allows A* to focus on promising paths and avoid exploring unpromising ones.

Limitations:

  • A* can be memory-intensive if there are many nodes in the open set.
  • The efficiency of A* heavily depends on the quality of the heuristic. An inaccurate heuristic can lead to suboptimal paths.

The A* algorithm is widely used in pathfinding and graph traversal problems where finding the shortest path is crucial.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment