Move over Dijkstra: New algorithm just rewrote 70 years of computer science | Hacker News Reader

Move over Dijkstra: New algorithm just rewrote 70 years of computer science

medium.com

37 pointsrobaato32 comments

Original paper: https://arxiv.org/abs/2504.17033

Previous discussion: https://news.ycombinator.com/item?id=44812695

Thanks!

Breaking the sorting barrier for directed single-source shortest paths - https://news.ycombinator.com/item?id=44812695 - Aug 2025 (51 comments)

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

[1] https://en.wikipedia.org/wiki/Contraction_hierarchies

[2] https://project-osrm.org/

[3] https://www.graphhopper.com/

OSRM 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.

Hi! 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

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 . 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"?

I 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.

Ah, I guess you mean this paper then: 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.

Yep, that’s the one. There are a number of follow-up papers that engineer individual aspects of the implementation.

Why don't you focus on the actual content instead of attacking its authorship? Your comment is clearly written by an AI.

You need to take a break from the internet for a while. You're getting far too worked up over a passing comment. It clearly wasn't dismissive of the content and, as pointed out, OP immediately followed the comment by talking about the content (I.e. saying it's a decent summary).

Some of us think that anything created by an AI should be labeled as such. Is that an inherently evil belief?

It is a little dumbfounding to compare the seeming emotionality/outrage of your posts with that which spurred it.

Your gaslighting comment is clearly written by AI even if it has some points that might appear to be valid at first glance. Given its authorship, it doesn't merit a response from a human. You need to take a break from the internet instead of continuing to spread your AI generated spam!

I 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.

There 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.

Identifying 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.

I 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.

Why "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-bro...

and:

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.

It is evil because it is intended to suppress discourse for irrelevant reasons. It is also deceptive because you don't exactly know the level of effort that went into it.

It should make no difference it's written by AI or not. One should evaluate and criticize content without regard to who or what has written it. Conversely, just because a human writes something should not and does not make it superior.

People like you shamelessly attempt to suppress a broad spectrum of writing whenever they find something to disagree with, by blaming it on AI. That's what's evil about it.

I'm not trying to suppress anything, but I want people to be aware. Conversely, I would gladly point out that an article on mathematics written by Terence Tao is likely to be high quality and insightful. Such guides are helpful in a world where not everyone has the time or energy to fully get to grips with the minutiae.

No, what you're doing is unfairly biasing and inciting people against AI. No author should be given a free pass. AI has done a lot more to improve my life than Terence Tao.

The way I see it, AI is a tool. Using that tool can speed up production but compromise quality and depth. Much like handcrafted furniture is higher quality than factory-produced. It's not unfair or biased to make people aware that a piece furniture is factory-produced. Likewise with AI content.

Firstly you have no hard evidence. People like you often make up that bad faith assertion to attack authors unfairly.

Secondly, almost all content is going to be produced in part with assistance from AI tools, not necessarily to write the content, but at least to discover and understand source materials for it. Would you say that a search engine was used? AI is the new search engine too.

Your assertion that using AI makes content worse is a false one. Many use it to make their content better.

Also, you originally perpetuated a false dichotomy. Content is typically going to be produced in collaboration with AI.

Instead of using your lazy attack, if you actually see a real issue with some content, why not just document any issue with the content in good faith with the mindset that the content were written by a human?

Consider what you are fighting. Do you think your fight has a future where your side will come out victorious such that humans write content without AI?

I think there's a good chance that human-crafted content by experts will have the kind of reputation that high-quality artisanal goods have today. But I'm not exactly fighting for anything, it really was an offhand comment that made up a tiny part of my take on the article.

I see absolutely no reason to be this upset at the OP's comment... unless you're the author (erm, publisher?) of the article. Are you?

> It should make no difference it's written by AI or not.

It absolutely should.

No, and I am not affiliated with the article or its author. Your attempt at gaslighting my point is noted.

It is plain wrong to make an unsubstantiated and unproven accusation, and even if were true, it's irrelevant to the topic at hand. Moreover, it demonstrates an unjustified anti-AI bias which is a separate problem.

Personally, I think you need to chill. He wasn’t “attacking” it, he was just commenting and includes his interpretation about it being from AI. Why don’t YOU just focus on the primary point of his comments instead of latching onto the AI part—or is it okay when you do it?

Users such as him routinely use the AI excuse to try to discredit valid posts without evidence. It is an altogether evil act, attempting to suppress valid discourse. This merits recognizance. I was only mocking this action. Even if something were to truly be written by AI, that is not a valid reason to try to discredit it. It's not okay for anyone to do it. Why ruin an otherwise excellent comment for no reason?

Anyone poked at this enough to see if it offers useful improvements at small scales? We use a ton of Dijkstra for various subproblems of pathfinding in video games, but the graphs don't tend to be huge (a few thousand nodes, maybe), or highly connected

My hunch would be to stick with Dijsktra (or A*). There's a bunch of additional routines here which appear to improve behaviour as the number of nodes becomes large, but very likely lead to large coefficients in the complexity.

https://archive.is/M9fyh

The challenge of implementing this for internet routing is that you'll probably need a whole new protocol implementation as part of either BGP (currently the protocol responsible for Internet routing between networks) or something entirely new. Let alone that BGP is a path vector protocol and not a link-state protocol that uses Dijkstra (like OSPF and IS-IS).

It might optimize internal routing but getting this standardised across vendors etc. is not impossible, but probably takes a long time to standardise/govern etc.

Why would that be? I don’t know how the version of sort() I use is implemented, but the results are the same as any other correct algorithm.

Reply on news.ycombinator.com