There are 312 487 500 potential paths (25K choose 2) and edge weights are variable-- the cost function is determined by user-configurable multipliers. So precomputing all paths in advance isn't feasible, unless I'm misunderstanding what you mean.
On Dec 27, 5:03 pm, "David Symonds" <dsymo...@gmail.com> wrote: > On Sat, Dec 27, 2008 at 5:16 AM, Amar Pai <jcrue...@gmail.com> wrote: > > I have a route planning webapp, written in Python, that uses > > Djikstra's algorithm to find the shortest path between two nodes in a > > directedgraph. I want to port this to AppEngine, but I'm not sure > > how to represent thegraph. Right now I'm using a dict of dict, G[pt] > > [pt] -> (edge data) where pt1/pt2 are coordinates and edge data is > > just some strings. Thegraphis cPickled and gets loaded on app > > startup. It has about 25K entries and the pickle file is 3 MB. I > > generate it offline, and it's read-only-- basically a large constant > > lookup table that gets repeatedly queried when the path planner > > runs. > > I'm not sure that's such a good fit. How about computing the shortest > paths between any two nodes offline, and simply looking them up? > > Dave. --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Google App Engine" group. To post to this group, send email to google-appengine@googlegroups.com To unsubscribe from this group, send email to google-appengine+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/google-appengine?hl=en -~----------~----~----~----~------~----~------~--~---
