What are Path Search Algorithms?
- Taking a more informal approach on the subject, taking away all the boring and theoretical game that applies in college when we study the subject on Graph Theory. Path Search Algorithms look for a single ideal, the minimum path. And to find this minimum path you will have to follow a set of rules for each type of algorithm that has been defined according to some study (work, theorem, anything done by a guy in the past that was widely accepted and tested) / em>
What types are there?
(Answering the part of the most used ones here too)
* There are several types of minimum path search algorithms, but for the purposes of studies we must stick to the main algorithms, which fall into quizzes, contests, and so on.
Wikipedia, a good summary on the major used.
- Dijkstra Algorithm - Solve the problem with a source vertex in graphs whose edges have a weight greater than or equal to zero. Without reducing
performance, this algorithm is able to determine the minimum path,
starting from a vertex of beginning v for all the other vertices of the
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 in a graph.
- Johnson's algorithm - Determines the distance between all the pairs of vertices of a graph, it can be faster than the algorithm of
Floyd-Warshall in sparse graphs. *
Examples and where are they used?
Path search algorithms do not just refer to examples of map links, an example that I really like to cite is a system that was made using several connections at distinct points to get to the final destination, a "tower."
The idea behind where the minimum path algorithms are used is you have the need to get to certain point with the highest possible speed. To solve this arrival, you will apply some of the algorithms listed above and check which one meets your need, this speaking in terms of algorithmic vision.
Observations:
The theoretical part of this subject is very extensive, until I came across questions as to why this discipline has such a theoretical background, the way was to read books and books in college to get the necessary grade. Looking for some books is always good, I studied the material a long time ago and I may have missed something important.