CODEWITHSUNDEEP
pythonsqlite
sokeefe
sokeefe

Reputation: 637

Looping on a relational database with Python

I'm trying to figure out a python loop that would find the minimum cost to go from point A to point B within a given dataset. For example, if someone wanted to fly from San Francisco to New York via the lowest cost with the below data. 

sql.keys
# [u'id', u'departure', u'arrival', u'cost']

for i in sql:
  print i
#(0, u'San Francisco', u'New York', 600)
#(1, u'Denver', u'Chicago', 100)
#(2, u'New York', u'DC', 100)
#(3, u'Chicago', u'New York', 200)
#(4, u'San Francisco', u'Denver', 200)

With the above example, I'm hoping that the result will return the below: 

(u'San Francisco', u'New York', 500)

Since someone can go between the two cities via SF -> Denver -> Chicago -> New York for 500 instead of flying direct for 600.

Thanks in advance!

Upvotes: 0

Views: 39

Answers (1)

Petar Ivanov
Petar Ivanov

Reputation: 93030

This is a standard graph problem for finding a shortest path in a graph.

The most famous algorithm is Dijkstra's.

If the data fits in memory, I would build an in memory graph and then apply the Dijkstra algorithm to it with starting node of 'San Francisco'. This would be faster than querying the database for each edge.

Upvotes: 1

Related Questions