Dijkstra's or A* for this situation

  • Context: Undergrad 
  • Thread starter Thread starter eboyle12
  • Start date Start date
Click For Summary
SUMMARY

The discussion centers on selecting the appropriate algorithm for finding the shortest path in a network of 100 routers modeled in MATLAB. The user is deciding between Dijkstra's algorithm and A* for this task, ultimately receiving confirmation that Dijkstra's algorithm is suitable. The key takeaway is the necessity of implementing a predecessor array to trace the shortest path from the destination back to the source. Relevant resources include a PDF on Dijkstra's algorithm and the book "Introduction to Algorithms" by Cormen.

PREREQUISITES
  • Understanding of graph theory concepts, specifically adjacency matrices
  • Familiarity with Dijkstra's algorithm and its implementation
  • Basic knowledge of MATLAB programming
  • Concept of predecessor arrays in pathfinding algorithms
NEXT STEPS
  • Implement Dijkstra's algorithm in MATLAB using an adjacency matrix
  • Study the concept and implementation of predecessor arrays for path reconstruction
  • Explore the A* algorithm and its heuristic functions for pathfinding
  • Read "Introduction to Algorithms" by Cormen for deeper insights into algorithm design
USEFUL FOR

Software developers, network engineers, and algorithm enthusiasts looking to optimize pathfinding in graph-based models, particularly in MATLAB environments.

eboyle12
Messages
1
Reaction score
0
I am doing some programming in matlab, specifically modeling tcp in matlab. I have a grid of 100 routers, they are connected to other routers in the cardinal direction as well as some random routers that are not adjacent. I need to find the shortest path from router a to router b. I already have a adjacency matrix, it is 100 by 100 and and each ordered pair represents the presence of an edge with 1 and no edge with a zero. My question is which algorithm to use to find the shortest path, most specifically the data i am looking for the algorithm to return is the next point in the shortest path to jump to. I am not sure if Dijkstra's or A* is appropriate in this situation as the descriptions and pseudo code i have found online is not quite clear. Can anyone help me out?
 
Physics news on Phys.org
I am not familiar with the A* algorithm. Dijkstra's algorithm should work for your problem. If you want to get the shortest path you have use a predecessor array (sometimes called previous array).

See here:
http://www.intag.org/downloads/ds_006.pdf
http://en.wikipedia.org/wiki/Dijkstra's_algorithm

Once you have the predecessor array you can go backwards from the goal to the source.
If you want to read more about Dijkstra's algorithm I recommend "Introduction to algorithms" by Cormen.
 

Similar threads

Undergrad Feynmann's connection machine model
  • · Replies 1 ·
Replies
1
Views
3K
MHB Finding Shortest Path in G: Dijkstra's Algorithm
  • · Replies 2 ·
Replies
2
Views
2K
MHB Find path to minimum cost from start to finish
  • · Replies 19 ·
Replies
19
Views
2K
Undergrad Shortest path problem with multiple goals on a grid
  • · Replies 2 ·
Replies
2
Views
2K
C data structures and algorithms - graph problem
  • · Replies 2 ·
Replies
2
Views
2K
Comp Sci Using Single Source Shortest Path Algorithm to find the longest path
  • · Replies 4 ·
Replies
4
Views
2K
Stress testing a wireless router
  • · Replies 17 ·
Replies
17
Views
3K
Undergrad Calculating the transform matrix
  • · Replies 1 ·
Replies
1
Views
2K
Optimal Path from source to multiple destinations
  • · Replies 3 ·
Replies
3
Views
2K
Graduate Half-face traversal on general polyhedra
  • · Replies 9 ·
Replies
9
Views
3K