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