Re: Representing a Graph in an RDB...again...(BUT DIFFERENT!!)

spuddd_at_gmail.com (Spud) wrote:

>I have browsed this group for about 2hours, and have seen many posts
>on the topic of graphs in RDBs, but i havent yet found one that
>answers my problem.
>
>Basically, I have a set of towns. Each town is connected to another
>town with a cost of travel. This seems simple enough right? Just a
>connected graph. One problem is that for every node A to C, one can
>also go C to A, so its bidirectional always. One can also start on any
>node.

[snip]

>Just having one weight per row makes it possible to do the calculation
>of shortest path, which i need.
>
>However, there is a spanner in the works - Certain links can only
>happen at certain times on certain days....eg A to C can only happen
>on thursdays and tuesdays at 2pm until 3pm. So one has to check an
>inputted time and then when calculated shortest path, ensure that one
>does not use edges that are unavaible at that time!!

[snip]

     This problem is generally known as the travelling salesman problem. There is no general solution known even without your additional timing constraints. IOW, you have to iterate through every possible solution to be sure that you have found the best.

     However, if you check the literature, you might find some approximations that will meet your needs.

Sincerely,

Gene Wirchenko

Computerese Irregular Verb Conjugation:

     I have preferences.
     You have biases.
     He/She has prejudices.