分页： 1 / 1
#1 老中搞出最短路径新算法
发表于 ： 2025年 8月 8日 16:19
由 moridin
#2 Re: 老中搞出最短路径新算法
发表于 ： 2025年 8月 8日 18:39
由 hci
文章呢？
#3 Re: 老中搞出最短路径新算法
发表于 ： 2025年 8月 8日 18:58
由 moridin
hci 写了： 2025年 8月 8日 18:39文章呢？
给了link 啊。英文的。
避免了排序，理论上比Dijkstra 快。
#4 Re: 老中搞出最短路径新算法
发表于 ： 2025年 8月 8日 19:10
由 hci
https://arxiv.org/abs/2504.17033
moridin 写了： 2025年 8月 8日 18:58
给了link 啊。英文的。
避免了排序，理论上比Dijkstra 快。
#5 Re: 老中搞出最短路径新算法
发表于 ： 2025年 8月 8日 20:22
由 skywalkur
美国文章都是一个模子：采访A，采访B，采访C，说了一堆，跟国内哪些歌颂先进工作者一样
#6 Re: 老中搞出最短路径新算法
发表于 ： 2025年 8月 8日 22:36
由 牛河梁
没有读文章。但显然这个问题意义很大。怎么强调都不为过。
#7 Re: 老中搞出最短路径新算法
发表于 ： 2025年 8月 9日 00:07
由 mmking
single-source shortest paths (SSSP)
Dijkstra是all pair shortest path
moridin 写了： 2025年 8月 8日 18:58
给了link 啊。英文的。
避免了排序，理论上比Dijkstra 快。
#8 Re: 老中搞出最短路径新算法
发表于 ： 2025年 8月 9日 06:41
由 jkxf
mmking 写了： 2025年 8月 9日 00:07
single-source shortest paths (SSSP)
Dijkstra是all pair shortest path
啥意思？一般大家的问题不都是single-source从纽约去DC怎么走最近？
All pair path是哪些例子？
#9 Re: 老中搞出最短路径新算法
发表于 ： 2025年 8月 9日 07:31
由 xexz
逐级马赛克，好手段。
#10 Re: 老中搞出最短路径新算法
发表于 ： 2025年 8月 9日 11:17
由 benw
嗯，理论意义不小，但实际意义不是很大。Dijkstra相当于是从起点逐渐外扩一个“圆”直到接触到终点，从起点到“圆”内所有点的最短路径都求解了。应用中可以有非常多的优化，实际效果应该强于这个新算法。
mmking 写了： 2025年 8月 9日 00:07
single-source shortest paths (SSSP)
Dijkstra是all pair shortest path
#11 Re: 老中搞出最短路径新算法
发表于 ： 2025年 8月 9日 15:20
由 TestCases
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.
#12 Re: 老中搞出最短路径新算法
发表于 ： 2025年 8月 9日 16:04
由 mmking
Aha, u r right
TestCases 写了： 2025年 8月 9日 15:20
Dijkstra is single-source. Floyd–Warshall is all pairs.
#13 Re: 老中搞出最短路径新算法
发表于 ： 2025年 8月 18日 11:52
由 madalpaca
这种用了N个engineering技巧去追求一点点算法复杂度改善的东西基本上实际上面不可能和Dijikstra这种一目了然的算法比。问题是如果要上技巧，那么还不如去具体环境里面搞提高更多。
这种就是为啥现在很多人觉得学术界做的东西没用的原因之一。