Path Finding Algorithms
Introduction to Path Finding Algorithms
Hey folks !! Welcome to our page which serves as your comprehensive guide to “Path Finding Algorithms” implemented in Python. From classic algorithms like Dijkstra’s and A* to more advanced techniques such as D* Lite and Swarm Intelligence, we will unravel the principles, implementation details, and practical applications of these algorithms.
Pathfinding algorithms are computational techniques designed to find the optimal or near-optimal path between two points in a network, graph, or grid. The goal is to determine the most effective route, minimizing traversal costs and maximizing overall efficiency.
Definition: "Path Finding" and its algorithms
- Pathfinding refers to the process of finding the most efficient or optimal path between two points in a given space, typically represented as a network, graph, grid, or map.
- Pathfinding algorithms are employed to determine the route that minimizes traversal costs, considering factors such as distance, obstacles, and potential constraints.
- The ultimate objective is to guide a system or agent from a starting point to a destination in the most effective manner, taking into account the characteristics of the environment in which the navigation occurs.
Why are pathfinding algorithms important?
Here are key reasons why pathfinding algorithms are important:
- Efficient Route Planning : Pathfinding algorithms help in determining the most efficient or optimal path between two points in a given environment.
- Game Development: In video games, characters and entities often need to navigate through virtual environments intelligently.
- Robotics and Autonomous Vehicles : These algorithms help them plan safe and efficient routes, avoiding obstacles and making decisions based on the surrounding context.
Different types of Path Finding Algorithms
Common Path Finding Algorithms are :
- Dijkstra’s Algorithm
- A* (A Star) Algorithm
- Breadth-First Search (BFS)
- Depth-First Search (DFS)
Advance Path Finding Algorithms are :
- D* Lite
- Bidirectional Search
- Swarm Intelligence Algorithms
Dijkstra's Algorithm
Dijkstra’s Algorithm is a weighted graph search algorithm that finds the shortest path between nodes in a graph, considering non-negative edge weights. It maintains a priority queue to continuously select and relax the closest unvisited node until the destination is reached.
Code :
import heapq
def dijkstra(graph, start, end):
distances = {node: float('infinity') for node in graph}
distances[start] = 0
priority_queue = [(0, start)]
while priority_queue:
current_distance, current_node = heapq.heappop(priority_queue)
if current_node == end:
return distances[end]
if current_distance > distances[current_node]:
continue
for neighbor, weight in graph[current_node].items():
distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(priority_queue, (distance, neighbor))
# Example usage:
graph_example = {
'A': {'B': 1, 'C': 4},
'B': {'A': 1, 'C': 2, 'D': 5},
'C': {'A': 4, 'B': 2, 'D': 1},
'D': {'B': 5, 'C': 1}
}
result = dijkstra(graph_example, 'A', 'D')
print("Shortest distance from A to D:", result)
Output :
# Example Output Shortest distance from A to D: 3
Explanation :
The output of Dijkstra’s algorithm is the shortest distance from the start node to all other nodes in the graph, along with the actual paths leading to each node. This means that the shortest distance from node ‘A’ to node ‘D’ in the given graph is 3 units.
Practical Example
Consider a road network where each road has a travel time (weight). Dijkstra’s algorithm could be used to find the shortest travel time between two locations, ensuring an optimal route in terms of time.
A* (A Star) Algorithm
The A* Algorithm is an informed search algorithm that combines the principles of Dijkstra’s Algorithm and a heuristic to guide the search efficiently. It uses a heuristic function to estimate the cost from the current node to the goal, prioritizing nodes with lower expected costs.
Code :
import heapq
import math
def heuristic(node, goal):
return math.sqrt((node[0] - goal[0])**2 + (node[1] - goal[1])**2)
def astar(graph, start, end):
open_set = [(0, start)]
came_from = {}
g_score = {start: 0}
while open_set:
current_cost, current_node = heapq.heappop(open_set)
if current_node == end:
path = []
while current_node in came_from:
path.append(current_node)
current_node = came_from[current_node]
return path[::-1]
for neighbor, cost in graph[current_node].items():
tentative_g_score = g_score[current_node] + cost
if neighbor not in g_score or tentative_g_score < g_score[neighbor]:
g_score[neighbor] = tentative_g_score
f_score = tentative_g_score + heuristic(neighbor, end)
heapq.heappush(open_set, (f_score, neighbor))
came_from[neighbor] = current_node
# Example usage:
graph_example = {
(0, 0): {(0, 1): 1, (1, 0): 1},
(0, 1): {(0, 0): 1, (1, 1): 1},
(1, 0): {(0, 0): 1, (1, 1): 1},
(1, 1): {(0, 1): 1, (1, 0): 1}
}
result = astar(graph_example, (0, 0), (1, 1))
print("Shortest path from (0, 0) to (1, 1):", result)
Output :
Shortest path from (0, 0) to (1, 1): [(0, 0), (0, 1), (1, 1)]
Explanation :
The output of the A* algorithm is typically the shortest path from the start node to the goal node, along with the cost or distance associated with that path. This means that the shortest path from the starting point (0, 0) to the goal point (1, 1) is through the sequence of grid points [(0, 0), (0, 1), (1, 1)]. The actual cost or distance could be calculated based on the weights associated with the edges in the graph.
Practical Example
In a grid-based game, A* can be employed to find the shortest path for a character to reach a destination, considering obstacles. The heuristic guides the search towards the goal, optimizing the pathfinding process.
Breadth-First Search (BFS) Algorithm
Breadth-First Search is an algorithm for traversing or searching tree or graph data structures. It explores all the vertices at the current depth before moving on to vertices at the next depth level. BFS is often used for unweighted graphs.
Code :
from collections import deque
def bfs(graph, start, end):
queue = deque([start])
visited = set([start])
while queue:
current_node = queue.popleft()
if current_node == end:
# Construct the path
path = [current_node]
while current_node != start:
current_node = visited[current_node]
path.append(current_node)
return path[::-1]
for neighbor in graph[current_node]:
if neighbor not in visited:
queue.append(neighbor)
visited[neighbor] = current_node
# Example usage:
graph_example = {
'A': ['B', 'C'],
'B': ['A', 'D'],
'C': ['A', 'D'],
'D': ['B', 'C']
}
result = bfs(graph_example, 'A', 'D')
print("Shortest path from A to D:", result)
Output :
Shortest path from A to D: ['A', 'B', 'D']
Explanation :
The output of the Breadth-First Search (BFS) algorithm is typically the shortest path from the start node to the goal node, represented as a sequence of nodes. This means that the shortest path from the start node ‘A’ to the goal node ‘D’ is through the sequence of nodes [‘A’, ‘B’, ‘D’]. This output represents the minimum number of edges or steps required to reach the goal node from the start node.
Practical Example
Consider a social network represented as a graph. BFS can be employed to find the shortest path of connections between two individuals, determining the fewest number of connections needed to reach from one person to another.
To Wrap it up:
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment