Path Finding Algorithms In Data Structure

What Are Path Finding Algorithms?

Path finding algorithms are used to solve the shortest path problems in graph theory. Path finding algorithms are try to find the best path given a starting point and ending point based on some predefined criteria.

Sourced from

https://images.app.goo.gl/j2BHzb4fRbJUYFjq5

Path finding is related to the how to identify the path that best meets some criteria (shortest, cheapest, fastest ,etc.) between two points in large network.

What Is The Shortest Path Problem Algorithms?

In graph theory, the shortest path problem is the problem of finding a path between two vertices/nodes in a graph such that the sum of the weights of its constituent edges is minimized.

What it is essentially trying to say is "Find the shortest path in between two points or nodes in a graph."

Examples /Types of Path Finding Algorithms

Here are some Example :

• Breadth First Search (BFS)
• Depth  First Search (DFS)

Breadth First Search (BFS)

Breadth first search is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root, and explores all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level.

 

Sourced From

https://images.app.goo.gl/k5rNibENCUKR3Dq28

• Worst Complexity: O(b^d)
• Space Complexity: O(b^d)
• Data Structure: Graph
• Class: Search Algorithm

Depth First Search (DFS)

Depth first search is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node and explores as far as possible along each branch before backtracking. 

Sourced From

https://images.app.goo.gl/6UJZ9XjWCD1k9R8fA

• Worst Complexity: O(b^d)
• Space Complexity: O(bd)
• Data Structure: Graph
• Class: Search Algorithm

Why Path Findings Are Important?

Path finding algorithms are important because they are used in applications like google maps, satellite navigation systems, routing packets over the internet. The usage of pathfinding algorithms isn’t just limited to navigation systems. The overarching idea can be applied to other applications as well.

Why Is Graph Or Graph Theory?

They are mathematical structures used to model pairwise relationships in between objects. A graph consists of nodes/vertices/points that are connected edges/links/lines. I know this may seem a little confusing but just look to the visual below for more clarification.

Sourced From

 https://en.wikipedia.org/wiki/Graph_theory

The circles with letters in them are nodes/vertices/points and the lines connecting/relating the circles are the edges/links/lines. The letters in the circles uniquely represent that circle. The numbers on the lines represent how much it will cost to move along that line.

Resources :

 Path Finding Algorithm : 

https://en.wikipedia.org/wiki/Pathfinding

Shortest Path Finding Algorithm :

https://en.wikipedia.org/wiki/Shortest_path_problem