9
In college studies, I came across the Path Search algorithms.
The theoretical part confused me a lot and I am limited to understand the uses of this algorithm in practice.
What Are Path Finding Algorithms?
What types exist?
Which are the most used?
In addition to the famous Google Maps, where more than these algorithms are used?
5
What Are Path Finding Algorithms?
They are algorithms that propose to solve the minimum path problem.
What types exist?
Algorithm by Dijkstra - Solves the problem with a source vertex at
graphs whose edges have a weight greater than or equal to zero. Without reducing the
performance, this algorithm is able to determine the minimum path,
starting from a vertex beginning v to all other vertices of
graph.
Bellman-Ford algorithm - Solves the problem for graphs with a source vertex and edges that may have negative weights.
Algorithm A* - a heuristic algorithm that calculates the minimum path
with a source vertex. 
Floyd-Warshall algorithm - Determines the distance between all pairs of vertices of a graph.
Johnson’s algorithm - Determines the distance between all pairs of vertices of a graph, may be faster than the Floyd-Warshall algorithm in sparse graphs.
Which are the most used?
Games make enough use of implementations of Dijkstra and To*.
In addition to the famous Google Maps, where more than these algorithms are used?
As mentioned, games make quite use of SPP algorithms (Shortest path problem).
Some architecture and usability solutions also make use of similar algorithms.
3
As the name itself says, are algorithms that seek to find the path of an X point to a Y point within a data structure, usually graphs.
There are all kinds, algorithms to search minimum path between two points, the maximum cost path, fastest path based on history...
I would not say the most used, but the most famous to determine the minimum path for example, are:
They are constantly used in maps as you have commented, they are also present in games, when for example the computer has to simulate paths depending on the level or not, briefly these algorithms can appear to solve logistics problems, computer and telecommunications networks, etc....
2
- Taking a more informal approach on the subject, taking away all the boring and theologian departure that applies in college when we study the subject on Graph Theory. Path Search algorithms search for a single ideal, the minimum path. And to find this minimum path you have to follow a set of rules for each type of algorithm that has been defined according to some study (work, theorem, anything elaborated by a guy in the past, that has been widely accepted and tested).
(Answering here the part of the most used also)
*There are several types of minimum path search algorithms, but for the purposes of studies we must stick to the main algorithms, which are the ones that fall into tests, contests and etc, are they:
Wikipedia, a good summary of the main used. - Dijkstra’s algorithm - Solves the problem with a source vertex in graphs whose edges have weight greater than or equal to zero. Without reducing the performance, this algorithm is able to determine the minimum path, starting from a vertex beginning v to all other vertices of graph.*
- Bellman-Ford algorithm - Solves the problem for graphs with a source vertex and edges that may have negative weights.
- Algorithm A? - a heuristic algorithm that calculates the minimum path with a source vertex.
- Floyd-Warshall algorithm - Determines the distance between all pairs of vertices of a graph.
- Johnson’s algorithm - Determines the distance between all pairs of vertices of a graph, may be faster than the algorithm of
Floyd-Warshall in sparse graphs.*
Path search algorithms don’t just stick to examples of links on maps, an example I like to cite is a system that was made using several connections at different points to reach the final destination, a "tower". The idea behind where minimum path algorithms are used is that you have to reach a certain point at the highest speed possible. To resolve this arrival, you will apply some of the algorithms listed above and check which one meets your need, this speaking in terms of vision in algorithms.
The theoretical part of this discipline is very extensive, until I came across with questions of why this discipline has such an extensive theoretical foundation, the way was to read books and books in college to get the necessary grade. Look for some book is always good, I studied the subject a long time and I may have missed something important.
1
There are several types of algorithms, the main ones being the search for the minimum path. One of the best known is djikstra is used in computer routing networks. Very common its use in graphs with the traveling salesman problem being one of the most popular.
Browser other questions tagged algorithm artificial-intelligence
You are not signed in. Login or sign up in order to post.