Dijkstra's or A* for this situation

  • Thread starter eboyle12
  • Start date
  • #1
1
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?
 

Answers and Replies

  • #2
703
13
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.
 

Related Threads on Dijkstra's or A* for this situation

Replies
4
Views
6K
Top