Path Finder

A web app to help visualizing typical graph searching algorithms

Live Demo • Development Stack • Brief Info About The Algorithms • Credits

Live Demo

You can play-around with the live demo of the project.

Development Stack

Brief Info About The Algorithms

• A* Search:

  

  A* (pronounced "A-star") is a graph traversal and path search algorithm, which is often used in many fields of computer science due to its completeness, optimality, and optimal efficiency.One major practical drawback is its {\displaystyle O(b^{d})}O(b^d) space complexity, as it stores all generated nodes in memory. Thus, in practical travel-routing systems, it is generally outperformed by algorithms which can pre-process the graph to attain better performance, as well as memory-bounded approaches; however, A* is still the best solution in many cases. -Wikipedia

• Dijkstra's Algorithm:

  

  Dijkstra's algorithm (or Dijkstra's Shortest Path First algorithm, SPF algorithm) is an algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later.

  The algorithm exists in many variants. Dijkstra's original algorithm found the shortest path between two given nodes,[5] but a more common variant fixes a single node as the "source" node and finds shortest paths from the source to all other nodes in the graph, producing a shortest-path tree. -Wikipedia

• Breadth First Search (BFS):

  

  Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a 'search key'), and explores all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level. -Wikipedia

• Depth First Search (DFS):

  

  Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking. -Wikipedia

• Best-First Search (Greedy):

  

  Best-first search is a search algorithm which explores a graph by expanding the most promising node chosen according to a specified rule. Judea Pearl described best-first search as estimating the promise of node n by a "heuristic evaluation function {\displaystyle f(n)}f(n) which, in general, may depend on the description of n, the description of the goal, the information gathered by the search up to that point, and most important, on any extra knowledge about the problem domain." Some authors have used "best-first search" to refer specifically to a search with a heuristic that attempts to predict how close the end of a path is to a solution, so that paths which are judged to be closer to a solution are extended first. This specific type of search is called greedy best-first search or pure heuristic search. -Wikipedia

Note: The GIF images are unashamedly taken from Wikipedia as well

Credits

• Daniel Shiffman's video resources on P5.js helped me a lot to get a clear understanding about the library.
• Clément Mihailescu's similar project inspired me a lot for the UI and the project itself
• P5.js The library behind the viz

You may also like...

• 8-Puzzle Using A* Search - Interactive way to solve the puzzle or get it solved by the AI

Stack Overflow @khalid-saifullah  ·  GitHub @khalidsaifullaah  ·  Facebook @ikhalidsaifullaah  ·  Twitter @k_saifullaah  ·  LinkedIn @khalidsaifullaah