Travelling Sales Person Theory - Shortest path between mustpass nodes


I am trying to find the shortest path that is required to fetch data about all test centres. Each test centre allows you to query upto 5 other test centres from that centre (e.g when logged in as test centre 1 you can fetch details about test centres 2,9,12,26,30) However I would then have to log into test centre 2 to fetch details about other centres e.g 10,13,16.

The dataset is concerning around 300 test centres.

My database structure is below:

CREATE TABLE IF NOT EXISTS testcentres_releationships (
testcentre1 int(10) NOT NULL,
testcentre2 int(10) NOT NULL,
PRIMARY KEY (home,local),
KEY local (local)

Many thanks in advance,


what’s wrong with this –

SELECT * FROM testcenters

that would return all rows, yes?

Sorry r937 i did not make myself clear. I am needing to output the correct order at which to query testcentres via curl with the relationships defined in the database.

oh, i see :blush:

i’m gonna predict that there’s no way to do this efficiently with SQL

The coding environment is PHP/MySQL if this facilitates matters.

Just thought id clarify things abit further. Am looking to find the value of all-pairs via the shortest path e.g find the shortest paths between every pair of nodes in the graph. Nodes in this case being the test centres of equal separation distance with the ability to start at any node. Floyd–Warshalls algorithm springs to mind however I am unable to find any examples under MySQL/PHP only PostgreSQL/PHP.

If you can find PostgreSQL/PHP examples, that should give you a good starting point. You might need to tweak syntax, but the functionality should be the same.