Shortest Path Algorithm

Question

Post reply

Shortest Path Algorithm

erdem1973

SSCommitted

Points: 1843
More actions
November 18, 2006 at 2:23 am

#115271

Hi Folks,
I have a database table named Stores that includes following columns
StoreID int,
StoreName varchar(50),
Region int
I want to create a new table named Roads which includes distance information of Store pairs:
Roads
Store1,Store2,Distance
How can I create this table. I want to import data of all combinations of these store pairs.
Please help

Viewing 12 posts - 1 through 11 (of 11 total)

You must be logged in to reply to this topic. Login to reply

Sergiy SSC Guru Points: 110208 More actions · Answer 1

SELECT T1.StoreID, T2.StoreID, CAST(NULL as real) as Distance

INTO dbo.Roads

FROM dbo.Stores T1

INNER JOIN dbo.Stores T2 ON T2.StoreID > T1.StoreID

Because distanse from Store2 to Store5 = distanse from Store5 to Store2 and distanse from Store2 to Store2 = 0 you need only sigle-side relation. It does not matter "<" or ">" you will use.

_____________
Code for TallyGenerator

jezemine SSCrazy Eights Points: 8059 More actions · Answer 2

in general, travel time between two points is not the same in both directions. most common example is airlines - because of prevailing winds it takes longer to fly to hawaii from seattle than the reverse. but maybe your app doesn't care about this little detail

---------------------------------------
elsasoft.org

Farrell Keough SSCoach Points: 17414 More actions · Answer 3

This is an "as the crow flies" approach. If you are using streets between stores within a given area, (i.e., from one location within a town to another location within the same or a different town) this may get more complicated...

I wasn't born stupid - I had to study.

jezemine SSCrazy Eights Points: 8059 More actions · Answer 4

indeed. have a look at Djikstra's or Floyd's algorithm for finding shortest path between nodes in a connected graph. I don't think it would be very efficient to implement these in t-sql however. If you have a very large graph, it woudl be better to implement in compiled code.

---------------------------------------
elsasoft.org

Sergiy SSC Guru Points: 110208 More actions · Answer 5

As I can see the question was not about travel time, but about distance.

Not even about travel distance, just distance.

I doon't think distance could depend on measuring direction. Unless you are under 5.

_____________
Code for TallyGenerator

jezemine SSCrazy Eights Points: 8059 More actions · Answer 6

hehe, ok.

I just assumed that the time is what you want to minimize because that's what most people care about.

if there's a shorter way on surface streets to get to a destination, do you take it, even if the freeway is 30mins faster? I don't think so.

---------------------------------------
elsasoft.org

Sergiy SSC Guru Points: 110208 More actions · Answer 7

I assumed from the question that distances will be loaded from somewhere, not calculated.

What they need is the prepared "pattern" to fill up with data.

_____________
Code for TallyGenerator

erdem1973 SSCommitted Points: 1843 More actions · Answer 8

Thank you very much for all friends,

We will enter road distances into a table and then the shortest path info will be calculated from this table.So all your comments will be useful for me

Thanks Again

jezemine SSCrazy Eights Points: 8059 More actions · Answer 9

fyi, Peter Larsson has implemented Djikstra in sql here:

http://www.sqlteam.com/forums/topic.asp?TOPIC_ID=77262

---------------------------------------
elsasoft.org

dclark SSC Eights! Points: 843 More actions · Answer 10

What is it that you want help with. Creating a table? Calculating the distance? Something else?

Wayne Lawton Hall of Fame Points: 3532 More actions · Answer 11

At the risk of sounding like an academic, are you sure you are using the right tool to solve the problem? Or phrased differently, are you using a hammer to turn a bolt?

Consider the problem constraints. You have locations, and roads between those locations. Last time I noticed, the city I live in had not moved very much in the last couple of hundred years. Likewise, roads between any two points in the city do not move very often at all. So who cares? We can use these constraints to our advantage, and thereby maximize the value of our tools (i.e. the database).

Databases do one thing and do it very well. They store large quantities of data, and retrieve it very quickly on demand. SQL provides the ability to programatically manipulate the data, but SQL is not really well suited to procedural logic such as pathfinding. So how do we leverage the strength of the database, while minimizing the shortcomings of SQL?

We implement a pathfinding algorithm in something like VB, C#, or other procedural language. For any two points, precompute the distance and store it in the DB along with the path that led to the distance. The only time the distance will need to be recomputed is if a particular road is unavailable for some reason, perhaps due to construction. Calculating the distance for a specific road that happens to be be blocked is much less effort for the DB and server than calculating the distance for every query. Further, specific roads may be temporarily blocked, but the vast majority of roads, and therefore distances, will be unchanged for very long periods of time.

I acknowledge that the volume of data may be significant, depending on the number of locations and roads. However, locations, roads, and distances all resolve down to integer values making for a very fast, indexable, retrieval process.

In summary, make sure you are using the right tool for the job, and using the tools in the most effective manner.