[pgrouting-users] All Nearest Neighbors

[Elijah Meeks]

The one-to-many pathfinding results can be constrained by distance, so the short answer is that there is a (potentially expensive) solution that you can go with right off the bat. It sounds to me like you need a breadth-first search, which I haven't seen for pgRouting but would be optimized for this kind of problem. I'd also like to see this implemented, so we could get ego networks and cost ego networks more efficiently than running 1-to-all and filtering the results.

-Elijah

----- Original Message -----
From: "Brian DeRocher" <brian at derocher.org>
To: "pgRouting users mailing list" <pgrouting-users at lists.osgeo.org>
Sent: Friday, June 6, 2014 12:56:25 PM
Subject: [pgrouting-users] All Nearest Neighbors

Does pgrouting have an algorithm to solve All Nearest Neighbors.  I'd rather not run Dijkstra's or A* n times.

I'm working on a project of build US congressional districts based on a k-means clustering of citizen residences.  But i want to use the driving distance for the distance function.  This is like asking, what's the closest post office for every person.  It's more work than A*, but it seems to me, less work than all pairs shortest path.  Am i wrong?

http://en.wikipedia.org/wiki/Nearest_neighbor_search#All_nearest_neighbors

If not, i'll work on it, where's a good place to start.

Brian

-- 
http://brian.derocher.org
http://mappingdc.org
http://about.me/brian.derocher
_______________________________________________
Pgrouting-users mailing list
Pgrouting-users at lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users