Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Dijkstra's or A* for this situation

  1. Nov 22, 2011 #1
    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?
  2. jcsd
  3. Nov 26, 2011 #2
    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:

    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook