SitePoint Sponsor

User Tag List

Results 1 to 7 of 7
  1. #1
    SitePoint Enthusiast
    Join Date
    Jul 2008
    Posts
    40
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    Travelling Sales Person Theory - Shortest path between mustpass nodes

    Hi,

    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`)
    ) ENGINE=InnoDB DEFAULT CHARSET=utf8;

    Many thanks in advance,

    Richard

  2. #2
    SQL Consultant gold trophysilver trophybronze trophy
    r937's Avatar
    Join Date
    Jul 2002
    Location
    Toronto, Canada
    Posts
    39,263
    Mentioned
    60 Post(s)
    Tagged
    3 Thread(s)
    Quote Originally Posted by r1ch View Post
    I am trying to find the shortest path that is required to fetch data about all test centres.
    what's wrong with this --
    Code:
    SELECT * FROM testcenters
    that would return all rows, yes?
    rudy.ca | @rudydotca
    Buy my SitePoint book: Simply SQL
    "giving out my real stuffs"

  3. #3
    SitePoint Enthusiast
    Join Date
    Jul 2008
    Posts
    40
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    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.

  4. #4
    SQL Consultant gold trophysilver trophybronze trophy
    r937's Avatar
    Join Date
    Jul 2002
    Location
    Toronto, Canada
    Posts
    39,263
    Mentioned
    60 Post(s)
    Tagged
    3 Thread(s)
    oh, i see

    i'm gonna predict that there's no way to do this efficiently with SQL
    rudy.ca | @rudydotca
    Buy my SitePoint book: Simply SQL
    "giving out my real stuffs"

  5. #5
    SitePoint Enthusiast
    Join Date
    Jul 2008
    Posts
    40
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    The coding environment is PHP/MySQL if this facilitates matters.

  6. #6
    SitePoint Enthusiast
    Join Date
    Jul 2008
    Posts
    40
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    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.

  7. #7
    Just Blow It bronze trophy
    DaveMaxwell's Avatar
    Join Date
    Nov 1999
    Location
    Mechanicsburg, PA
    Posts
    7,265
    Mentioned
    115 Post(s)
    Tagged
    1 Thread(s)
    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.
    Dave Maxwell - Manage Your Site Team Leader
    My favorite YouTube Video! | Star Wars, Dr Suess Style
    Learn how to be ready for The Forums' Move to Discourse


Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •