Shortest path finding algorithms

  • Thread starter Thread starter shashmehro
  • Start date Start date
  • Tags Tags
    Algorithms Path
Click For Summary
SUMMARY

The discussion centers on finding efficient algorithms for determining the shortest path in a maze, specifically for a project involving a mouse navigating to the center. Participants noted that Dijkstra's algorithm is insufficient for this task, and alternatives like flood fill present programming complexities. A suggestion was made to explore the "Knapsack problem," which is an optimization tree search algorithm that is easier to implement in this context.

PREREQUISITES
  • Understanding of graph theory and pathfinding algorithms
  • Familiarity with Dijkstra's algorithm and its limitations
  • Basic programming skills for implementing algorithms
  • Knowledge of optimization techniques in algorithm design
NEXT STEPS
  • Research the implementation of the Knapsack problem as an optimization tree search algorithm
  • Explore A* search algorithm for efficient pathfinding in mazes
  • Study the complexities and applications of flood fill algorithm
  • Investigate heuristic methods for maze navigation
USEFUL FOR

Students, software developers, and researchers interested in algorithm design, particularly those focused on pathfinding and optimization in computational problems.

shashmehro
Messages
3
Reaction score
0
hello folks...
my frnds and I have a project in which we have to find the shortest path possible for a mouse to traverse to the middle of the maze(any random maze)...we have understood that simply applying djikstra`s would not work...also prevalent algorithms like floodfill have a level of complexity which is not easy to program with...any suggestions or any algorithms which u guys can suggest?
 
Technology news on Phys.org
Try with the "Knapsack problem", it is a optimization tree search algorithm which is easy to
implement on a computer.
 

Similar threads

MHB Find path to minimum cost from start to finish
  • · Replies 19 ·
Replies
19
Views
2K
Non youtube courses and paid textbooks to learn algorithms?
  • · Replies 8 ·
Replies
8
Views
4K
Challenge: Find the minimum amount of draws possible for a list of integers
  • · Replies 9 ·
Replies
9
Views
3K
MHB Counting shortest paths in a non-directed graph using BFS
  • · Replies 1 ·
Replies
1
Views
2K
What is the fastest algorithm for finding large prime numbers?
  • · Replies 14 ·
Replies
14
Views
3K
Comp Sci Shortest path problem in bipartite graph
  • · Replies 1 ·
Replies
1
Views
2K
Shortest path finding algorithms
  • · Replies 2 ·
Replies
2
Views
2K
MHB Find the greatest of the shortest paths
  • · Replies 7 ·
Replies
7
Views
3K
High School Is the Geometry/Topology of Mazes a thing?
  • · Replies 18 ·
Replies
18
Views
3K
Algorithms learning materials and exercises
  • · Replies 4 ·
Replies
4
Views
1K