News for hackers. Stuff that matters.
Re:Show HN: Eppstein’s k shortest paths in the web browser w... by ctcliff on Friday July 29, 2016 @08:49PM (#12191092)
Yeah, that was an unpleasant surprise when I started plugging in the street map data :D

I'm experimenting with other algorithms and will post some (hopefully) more interesting results soon.

Re:Show HN: Eppstein’s k shortest paths in the web browser w... by danpat on Saturday July 30, 2016 @10:04AM (#12193005)
A plug for one of my co-workers who recently finished his PhD on alternative route finding:

http://algo2.iti.kit.edu/documents/Dissertation_Kobitzsch_Mo...

Choice quote from page 50:

k-Shortest Path. A, at the first glance reasonable, approach to alternative routes is the k-shortest path problem [Yen71]. The basic notion behind the problem, which has been studied quite extensively (e.g. [Shi79, Epp94, Epp98, Rup97]), is that next to the shortest path itself, slightly suboptimal paths will offer good alternatives. While this idea seems valid for specific networks2, it has been described as less effective [BDGS11] in the context of alternative routes in road networks. It is rather unlikely to find a good alternative route among the first few hundred paths. Jumping off the highway at a ramp and directly returning back onto it does not take much time compared to the full journey. Doing this at every possible combination of ramps might already contribute a large number of possible paths that are only slightly worse than the original shortest path. This directly implies that we might need a very large value for k before we can report a reasonable alternative route.

Re:Show HN: Eppstein’s k shortest paths in the web browser w... by csom on Saturday July 30, 2016 @12:44AM (#12191680)
you may want to look at: Alternative Routes in Road Networks Ittai Abraham, Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck https://www.microsoft.com/en-us/research/wp-content/uploads/...
Re:Show HN: Eppstein’s k shortest paths in the web browser w... by pmiller2 on Sunday July 31, 2016 @03:19AM (#12196070)
You can also change the definition of "shortest" by weighting roads by speed limit. I don't know if the data for that is easy to come by, but you can always use some arbitrary weights to get roughly the same effect.
Re:Show HN: Eppstein’s k shortest paths in the web browser w... by detaro on Friday July 29, 2016 @08:51PM (#12191099)
> will post some (hopefully) more interesting results soon.

Your blog could use an RSS feed or some other way to get notified of updates then ;)