CODEWITHSUNDEEP
phpmysql
Billy R.
Billy R.

Reputation: 13

Calculating shortest path between two "locations" via PHP from a MySQL db

I'm trying to figure out the best method of getting/displaying the shortest distance between multiple locations. To best explain this think of it as a map and use the following below. All of the distances and paths from each location would be already put in a MySQL database.

Locations(Letter -> Locations it can reach. and distance/time in [])

A -> B [5]
A -> C [4]
B -> Z [1]
C -> Z [50]

So A can go to B and takes 5 minutes. While going A to C takes 4 minutes.

Now what I'm trying to figure out is lets say someone says they are currently at location A and want to get to Z. How can I get the system to go through the database and determine that A -> B -> Z is the shortest path compared to A -> C -> Z.

I was originally thinking of doing a loop on each system but this setup is going to contain hundreds of different locations and paths. So I just can already see it creating infinite loops the second it follows a path that leads back to the starting position.

Maybe it is impossible.

Any help or suggestions would be much appreciated!

Upvotes: 1

Views: 1618

Answers (1)

Chadwick
Chadwick

Reputation: 12663

The Shortest Path Problem can be solved with numerous algorithms. Dijkstra is the classic:

  1. Assign to every node a distance value. Set it to zero for our initial node and to infinity for all other nodes.
  2. Mark all nodes as unvisited. Set initial node as current.
  3. For current node, consider all its unvisited neighbors and calculate their tentative distance (from the initial node). For example, if current node (A) has distance of 6, and an edge connecting it with another node (B) is 2, the distance to B through A will be 6+2=8. If this distance is less than the previously recorded distance (infinity in the beginning, zero for the initial node), overwrite the distance.
  4. When we are done considering all neighbors of the current node, mark it as visited. A visited node will not be checked ever again; its distance recorded now is final and minimal.
  5. If all nodes have been visited, finish. Otherwise, set the unvisited node with the smallest distance (from the initial node) as the next "current node" and continue from step 3.

Upvotes: 6

Related Questions