7 ms·
The linked medium post is clearly written by an AI but I think it does a decent job at summarising the results. Glancing through the paper on ArXiv, it feels li
by n4r9 1y ago
The linked medium post is clearly written by an AI but I think it does a decent job at summarising the results. Glancing through the paper on ArXiv, it feels like they've cleverly combined speed-up techniques from variations of Dijkstra invented over the years.
The Thresh X2 [0] algorithm - for example - does away with the priority queue that is the bottleneck in Dijkstra. Instead, it iteratively runs a "label-correcting" routine over increasing search radii until the target is hit. I only learnt about this algorithm this year and can't find much about it online, although I've heard that it's sometimes used in videogames.
Then there's Contraction Hierarchies [1], used by many modern routing engines (such as OSRM [2] or GraphHopper [3]). This involves a slow pre-processing step in which nodes are put into a hierarchy of "importance", allowing a modified query-time routine which is orders of magnitude faster than Dijkstra. Recent work on this has also resulted in query-time routines that eliminate priority queues entirely. However, this assumes a fairly static road graph over which many requests are run.
In the linked algorithm, they seem to have an iteratively increasing radii and a routine which applies Bellman-Ford to identify "important" nodes. As I understand it, this decreases the number of nodes that need to be inserted into the priority queue.
[0] https://dlnext.acm.org/doi/10.1016/0167-6377%2887%2990053-8 https://dlnext.acm.org/doi/10.1016/0167-6377%2887%2990053-8
[1] https://en.wikipedia.org/wiki/Contraction_hierarchies https://en.wikipedia.org/wiki/Contraction_hierarchies
[2] https://project-osrm.org/ https://project-osrm.org/
[3] https://www.graphhopper.com/ https://www.graphhopper.com/
- DennisL123 1y agoOSRM founder, here. Yes, you are right, many of the speedup techniques are related. My personal opinion is, tho, that looking at the identification of important nodes is best captured by the ideas of applying partitioning to multi-level dijkstra and by what’s called hub-labels. The latter has a close relationship to Contraction Hierarchies.
- n4r9 1y agoHi! If I remember rightly, you can run contraction hierarchies but stop short of the full contraction, and use the core vertices as "hubs"? Hope you don't mind but I took a little look at your posting history and saw this: https://news.ycombinator.com/item?id=41954120 https://news.ycombinator.com/item?id=41954120 I've been researching this lately, as we've recently implemented traffic patterns in our routing model and are just now working on live traffic updates. The easiest way to adapt our existing code looks like Customizable Contraction Hierarchies. There's a really nice review paper here: https://arxiv.org/abs/2502.10519 https://arxiv.org/abs/2502.10519 . The technique is to apply nested dissections to build a "metric-independent" hierarchy based purely on connectivity, which gives a decent quality of contraction regardless of transit times. Is that what you mean by decomposing the network into "cells"?
- DennisL123 1y agoI was referring to variants of Customizable Route Planning. Easiest to implement is likely the partitioner of Sommer et al, and a unidirectional multi-level dijkstra.
- n4r9 1y agoAh, I guess you mean this paper then: https://www.microsoft.com/en-us/research/wp-content/uploads/2013/01/crp_web_130724.pdf https://www.microsoft.com/en-us/research/wp-content/uploads/... There are many similarities between this approach and customisable contraction hierarchies. The latter allows a particularly elegant query-time algorithm involving only a couple of linear sweeps, I suspect even in the many-many scenario.
- DennisL123 1y agoYep, that’s the one. There are a number of follow-up papers that engineer individual aspects of the implementation.
- OutOfHere 1y agoWhy don't you focus on the actual content instead of attacking its authorship? Your comment is clearly written by an AI.
- n4r9 1y agoI did say it provides a decent summary. I write my own posts except where I explicitly copypaste a response from an LLM. In fact I just asked Claude Code and ChatGPT about the Thresh X2 algorithm and they couldn't even descibe it to me.
- OutOfHere 1y agoThere you go, attacking AI again, first for it producing content, and now for it not producing content. It is a palace of absurdity you have built. Maybe just try keeping AI out of your discussion.
- n4r9 1y agoIdentifying AI is useful to others. Especially in academic topics (where it is less reliable) or where text lacks a disclaimer. I do so without meaning to criticise AI itself. I'm sorry if this is a sensitive topic for you, but I think you're reading too much into what I'm saying.
- OutOfHere 1y agoI have seen lots of biased hateful users such as yourself that falsely attempt to discredit valid posts by claiming they're written by AI. It's extremely dumb and evil, is not backed any evidence, and is irrelevant to the post. Even if the post to actually be written by AI, that is no reason to use that assertion to try to discredit it. It ruins an otherwise excellent comment.
- n4r9 1y agoWhy "evil"? I'm pretty confident they're heavily (if not fully) relying on LLM-generated text. Maybe they're drafting it themselves first and getting an LLM to refine. I found some recent articles by the same author which gave me the same reaction: https://medium.com/@kanishks772/computer-scientists-just-broke-50-years-of-sorting-algorithms-1e8c06ab98ac https://medium.com/@kanishks772/computer-scientists-just-bro... and: https://medium.com/@kanishks772/why-your-next-gps-might-use-this-2025-algorithmic-breakthrough-07c9b80ffd34 https://medium.com/@kanishks772/why-your-next-gps-might-use-... They seem to have a process for grabbing a research paper, getting an LLM to summarise it, adding AI-generated images and pseudo code, and publishing it. There are lots of parallels in describing fundamental breakthroughs overturning decades of conventional wisdom. And it has the same clipped bullet lists with sound bite phrases, and slideshow style headings. It's extremely reminiscent of what happens when I ask Claude to give me a summary of something. As a general note, I do think it best to take any article written by AI with a pinch of salt. Much like you should closely review any code they write. It's not at the level of a human expert, but it's trained to convince you that it is one.