老中搞出最短路径新算法

[moridin]

链接在这里：https://www.quantamagazine.org/new-meth ... -20250806/

[hci]

文章呢？

[moridin]

文章呢？

给了link 啊。英文的。

避免了排序，理论上比Dijkstra 快。

[hci]

https://arxiv.org/abs/2504.17033

给了link 啊。英文的。

避免了排序，理论上比Dijkstra 快。

[skywalkur]

美国文章都是一个模子：采访A，采访B，采访C，说了一堆，跟国内哪些歌颂先进工作者一样

[牛河梁]

没有读文章。但显然这个问题意义很大。怎么强调都不为过。

[mmking]

single-source shortest paths (SSSP)

Dijkstra是all pair shortest path

给了link 啊。英文的。

避免了排序，理论上比Dijkstra 快。

[jkxf]

single-source shortest paths (SSSP)

Dijkstra是all pair shortest path

啥意思？一般大家的问题不都是single-source从纽约去DC怎么走最近？

All pair path是哪些例子？

[xexz]

逐级马赛克，好手段。

[benw]

嗯，理论意义不小，但实际意义不是很大。Dijkstra相当于是从起点逐渐外扩一个“圆”直到接触到终点，从起点到“圆”内所有点的最短路径都求解了。应用中可以有非常多的优化，实际效果应该强于这个新算法。

single-source shortest paths (SSSP)

Dijkstra是all pair shortest path

[TestCases]

single-source shortest paths (SSSP)

Dijkstra是all pair shortest path

Dijkstra is single-source. Floyd–Warshall is all pairs.

[mmking]

Aha, u r right

Dijkstra is single-source. Floyd–Warshall is all pairs.

[madalpaca]

这种用了N个engineering技巧去追求一点点算法复杂度改善的东西基本上实际上面不可能和Dijikstra这种一目了然的算法比。问题是如果要上技巧，那么还不如去具体环境里面搞提高更多。

这种就是为啥现在很多人觉得学术界做的东西没用的原因之一。