New Method Is the Fastest Way To Find the Best Routes (www.quantamagazine.org)
from misk@piefed.social to programming@programming.dev on 06 Aug 20:26
https://piefed.social/post/1120594

Archive: archive.ph/…/new-method-is-the-fastest-way-to-fin…

#programming

threaded - newest

TheAgeOfSuperboredom@lemmy.ca on 06 Aug 20:59 next collapse

Very cool! Looks like the paper is here: arxiv.org/abs/2504.17033

TehPers@beehaw.org on 07 Aug 01:08 next collapse

This is awesome! I’m reading through their paper right now, and might try to implement it to see how it works in practice.

TehPers@beehaw.org on 08 Aug 05:36 collapse

In case anyone’s curious, still working on it. It’s not as simple as something like Dijkstra’s algorithm.

What’s really interesting is the requirement that it seems to place on the graph itself. From what I can tell, the graph it wants to use is a graph where each node has a maximum in-degree of 2 and maximum out-degree of 2, with a total degree of no greater than 3. A traditional di-graph can be converted to this format by splitting each node into a strongly connected cycle of nodes, with each node in the cycle containing the in-edge and out-edge needed to maintain that cycle (with weights of 0) plus one of the previous edges.

Theorerically, this invariant can be held by the graph data structure itself by adding nodes as needed when adding edges. That’s what my implementation is doing to avoid having the cost of converting the graph each time you run the algorithm. In this case, one of these node cycles represents your higher level concept of a node (which I’m calling a node group).

The block-based list is also interesting, and I’ve been having trouble converting it to a data structure in code. I’m still working through the paper though, so hopefully that isn’t too bad to get done.

01189998819991197253@infosec.pub on 07 Aug 01:49 collapse

We care about your data, and we’d like to use cookies to give you a smooth browsing experience. Please agree and read more about our privacy policy.

At least they’re not hiding the fact that couldn’t care less about your privacy, and only care about your data. At least that…