老中搞出最短路径新算法

moridin · 帖子由 **moridin楼主** » 2025年 8月 8日 16:19

hci · 帖子由 **hci（海螺子）** » 2025年 8月 8日 18:39

文章呢？

moridin · 帖子由 **moridin楼主** » 2025年 8月 8日 18:58

hci 写了： 2025年 8月 8日 18:39文章呢？

给了link 啊。英文的。

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

hci · 帖子由 **hci（海螺子）** » 2025年 8月 8日 19:10

moridin 写了： 2025年 8月 8日 18:58 给了link 啊。英文的。

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

skywalkur

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

牛河梁

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

mmking · 帖子由 **mmking（上水）** » 2025年 8月 9日 00:07

single-source shortest paths (SSSP)

Dijkstra是all pair shortest path

moridin 写了： 2025年 8月 8日 18:58 给了link 啊。英文的。

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

jkxf · 帖子由 **jkxf** » 2025年 8月 9日 06:41

mmking 写了： 2025年 8月 9日 00:07 single-source shortest paths (SSSP)

Dijkstra是all pair shortest path

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

All pair path是哪些例子？

xexz · 帖子由 **xexz** » 2025年 8月 9日 07:31

逐级马赛克，好手段。

benw · 帖子由 **benw（BenW）** » 2025年 8月 9日 11:17

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

mmking 写了： 2025年 8月 9日 00:07 single-source shortest paths (SSSP)

Dijkstra是all pair shortest path

TestCases · 帖子由 **TestCases** » 2025年 8月 9日 15:20

mmking 写了： 2025年 8月 9日 00:07 single-source shortest paths (SSSP)

Dijkstra是all pair shortest path

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

mmking · 帖子由 **mmking（上水）** » 2025年 8月 9日 16:04

Aha, u r right

TestCases 写了： 2025年 8月 9日 15:20 Dijkstra is single-source. Floyd–Warshall is all pairs.

madalpaca

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

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

新未名空间