老中搞出最短路径新算法

版主: hci

回复
moridin楼主
著名写手
著名写手
帖子互动: 54
帖子: 322
注册时间: 2024年 12月 13日 13:09

#1 老中搞出最短路径新算法

帖子 moridin楼主 »


+1.00 积分 [版主 hci 发放的奖励]
I walked in the valley of shadow of death,
Yet I had no fear;
For I was the meanest :twisted: over there.

标签/Tags:
头像
hci(海螺子)
论坛支柱
论坛支柱
帖子互动: 475
帖子: 10058
注册时间: 2022年 7月 22日 15:29

#2 Re: 老中搞出最短路径新算法

帖子 hci(海螺子) »

文章呢?
moridin楼主
著名写手
著名写手
帖子互动: 54
帖子: 322
注册时间: 2024年 12月 13日 13:09

#3 Re: 老中搞出最短路径新算法

帖子 moridin楼主 »

hci 写了: 2025年 8月 8日 18:39文章呢?
给了link 啊。英文的。

避免了排序,理论上比Dijkstra 快。
I walked in the valley of shadow of death,
Yet I had no fear;
For I was the meanest :twisted: over there.
头像
hci(海螺子)
论坛支柱
论坛支柱
帖子互动: 475
帖子: 10058
注册时间: 2022年 7月 22日 15:29

#4 Re: 老中搞出最短路径新算法

帖子 hci(海螺子) »

https://arxiv.org/abs/2504.17033
moridin 写了: 2025年 8月 8日 18:58 给了link 啊。英文的。

避免了排序,理论上比Dijkstra 快。
skywalkur(温柔1刀)
职业作家
职业作家
帖子互动: 57
帖子: 665
注册时间: 2023年 7月 14日 02:03

#5 Re: 老中搞出最短路径新算法

帖子 skywalkur(温柔1刀) »

美国文章都是一个模子:采访A,采访B,采访C,说了一堆,跟国内哪些歌颂先进工作者一样
x1 图片
头像
牛河梁(别问我是谁)
论坛元老
论坛元老
2023年度十大优秀网友
2024年度优秀版主
牛河梁 的博客
帖子互动: 1547
帖子: 27707
注册时间: 2022年 11月 17日 21:21
联系:

#6 Re: 老中搞出最短路径新算法

帖子 牛河梁(别问我是谁) »

没有读文章。但显然这个问题意义很大。怎么强调都不为过。
头像
mmking(上水)
论坛支柱
论坛支柱
帖子互动: 1328
帖子: 9603
注册时间: 2023年 1月 25日 05:10

#7 Re: 老中搞出最短路径新算法

帖子 mmking(上水) »

single-source shortest paths (SSSP)

Dijkstra是all pair shortest path
moridin 写了: 2025年 8月 8日 18:58 给了link 啊。英文的。

避免了排序,理论上比Dijkstra 快。
这个煎饼多少钱? :D viewtopic.php?t=833307

凡所有相,皆是虚妄

图片
jkxf
职业作家
职业作家
帖子互动: 55
帖子: 650
注册时间: 2025年 2月 9日 09:04

#8 Re: 老中搞出最短路径新算法

帖子 jkxf »

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

Dijkstra是all pair shortest path
啥意思?一般大家的问题不都是single-source从纽约去DC怎么走最近?

All pair path是哪些例子?
xexz
论坛精英
论坛精英
帖子互动: 310
帖子: 5899
注册时间: 2022年 7月 30日 11:48
联系:

#9 Re: 老中搞出最短路径新算法

帖子 xexz »

逐级马赛克,好手段。
benw(BenW)
正式写手
正式写手
帖子互动: 12
帖子: 187
注册时间: 2022年 8月 24日 18:04

#10 Re: 老中搞出最短路径新算法

帖子 benw(BenW) »

嗯,理论意义不小,但实际意义不是很大。Dijkstra相当于是从起点逐渐外扩一个“圆”直到接触到终点,从起点到“圆”内所有点的最短路径都求解了。应用中可以有非常多的优化,实际效果应该强于这个新算法。
mmking 写了: 2025年 8月 9日 00:07 single-source shortest paths (SSSP)

Dijkstra是all pair shortest path
x1 图片
TestCases
论坛精英
论坛精英
帖子互动: 291
帖子: 8290
注册时间: 2023年 6月 26日 22:20

#11 Re: 老中搞出最短路径新算法

帖子 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.
x1 图片
头像
mmking(上水)
论坛支柱
论坛支柱
帖子互动: 1328
帖子: 9603
注册时间: 2023年 1月 25日 05:10

#12 Re: 老中搞出最短路径新算法

帖子 mmking(上水) »

Aha, u r right
TestCases 写了: 2025年 8月 9日 15:20 Dijkstra is single-source. Floyd–Warshall is all pairs.
这个煎饼多少钱? :D viewtopic.php?t=833307

凡所有相,皆是虚妄

图片
回复

回到 “葵花宝典(Programming)”