What are Path Search Algorithms?

9

In college studies, I came across Pathfinder algorithms.

The theoretical part confused me a lot and I'm limited to understand the uses of this algorithm in practice.

  • What are Path Search Algorithms?

  • What types are there?

  • Which are the most used?

  • In addition to the famous Google in Google Maps, where else are these algorithms used?

asked by anonymous 10.04.2017 / 19:28

4 answers

5
  

What are Path Search Algorithms?

They are algorithms that propose to solve the problem of the minimum path .

  

What types are there?

From the Wikipedia article :

  • Dijkstra Algorithm - Solve the problem with a vertex-source 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 - Solve the problem for graphs with one vertex-source and edges that can have negative weights.

  • Algorithm A * - a heuristic algorithm that calculates the minimum path with a vertex-source.

  • Floyd-Warshall Algorithm - Determines the distance between all pairs of vertices of a graph.

  • Johnson algorithm - Determines the distance between all pairs of vertices in a graph, it can be more faster than the Floyd-Warshall algorithm in sparse graphs.

  

Which are the most used?

Games make extensive use of Dijkstra implementations and A * .

  

In addition to the famous Google in Google Maps, where else are these algorithms used?

As mentioned, games make a lot of SPP algorithms ( Shortest path problem ).

Some architecture and usability solutions also make use of similar algorithms.

    
10.04.2017 / 19:51
3

What are they?

As the name implies, they are algorithms that seek to find the path from an X point to a point Y within a data structure, usually graphs .

What types are there?

There are a wide variety of algorithms to search for minimum path between two points, the max cost path , faster path based on history ...

Which are the most used?

I would not say the most used, but the most famous to determine the minimum path for example, are:

Where else are they used?

They are constantly used in maps as you yourself commented, 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 problems of logistics, computer networks and telecommunications, etc ...

    
10.04.2017 / 19:52
2

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.

    
10.04.2017 / 19:57
1

There are several types of algorithms, the main ones being the minimum path search. One of the best known is that djikstra is used in computer routing networks. Very common its use in graphs with the traveling clerk problem being one of the most popular.

    
10.04.2017 / 19:38