C# 狄克斯特拉算法方法 C#如何实现Dijkstra最短路径算法

星涛小哥_4330

星涛小哥_4330

2026-02-02

899人浏览

原创

应使用 long[] 距离数组和 long.MaxValue 初始化,避免 int 溢出;允许多次入队同一节点,出队时用 distances[current] != currentPriority 过滤过期条目。

c# 狄克斯特拉算法方法 c#如何实现dijkstra最短路径算法

用 PriorityQueue 实现 Dijkstra 的核心逻辑

.NET 6+ 自带的 PriorityQueue 是实现 Dijkstra 最自然的选择,它替代了手动维护最小堆或排序列表的麻烦。关键不是“怎么写循环”,而是确保每次出队的是当前已知最短距离的节点——这依赖于入队时传入的 TPriority(即距离值)严格单调非负,且更新时**不修改已入队节点的优先级**(PriorityQueue 不支持降键操作)。

所以标准做法是:允许同一节点多次入队,但第一次出队即为最短路径,后续再遇到该节点直接跳过。

  • 图用 Dictionary> 表示,节点用整数 ID(如 0 ~ n-1)
  • 初始化距离数组 distances 全为 int.MaxValue,起点设为 0
  • 入队格式: queue.Enqueue(nodeId, distances[nodeId])
  • 出队后检查 if (distances[current] != currentPriority) continue; 过滤过期条目

int.MaxValue 作为无穷大带来的溢出风险

当边权较大(比如接近 int.MaxValue / 2)且路径含多条边时,累加 distances[u] + weight 可能溢出为负数,导致错误松弛甚至死循环。这不是理论问题,真实数据中容易触发。

  • 不要用 int.MaxValue 做初始距离,改用 long.MaxValue 并把距离数组声明为 long[]
  • 边权本身可以仍是 int,但所有比较和加法需提升到 long
  • 如果必须用 int,至少加溢出检查:if (distances[u] != int.MaxValue && weight

重建最短路径而非只算距离

多数实际场景需要知道具体走哪几步,不只是一个数字。Dijkstra 本身不输出路径,但可以在松弛时同步记录前驱节点。

logos-node
logos-node

在 Linux x86_64 上安装、更新或检查 Logos 区块链测试网验证节点。用于用户需要搭建 Logos 节点时使用。

下载
  • 额外维护 int[] previous = new int[n],初始化为 -1
  • 当 distances[u] + w 成立时,除了更新距离,还要执行 previous[v] = u
  • 从终点倒推回起点:用 Stack 收集节点,避免递归或反转数组
  • 注意:若 previous[end] == -1,说明不可达,别强行构造路径

稀疏图用邻接表,稠密图考虑是否值得换 Array 手写堆

PriorityQueue 平均时间复杂度是 O((V+E) log V),对稀疏图足够好;但若边数 E 接近 V²(比如全连接网格),log V 开销会明显,而手写二叉堆(用 int[] 存储)可减少对象分配和泛型开销。

  • 99% 的业务场景直接用 PriorityQueue,可读性和维护性远胜微小性能差异
  • 只有在高频调用(如每秒数百次)、节点数 > 10⁵、且 profiling 确认堆操作是瓶颈时,才考虑替换
  • 别用 SortedSet 模拟优先队列——它不支持重复距离,且删除任意元素是 O(n)

实际编码中最容易被忽略的是溢出处理和过期节点过滤——这两个点一旦出错,结果既不报异常也不提示,只是静默返回错误路径。

相关文章

PHP速学视频免费教程(入门到精通)
PHP速学视频免费教程(入门到精通)

PHP怎么学习?PHP怎么入门?PHP在哪学?PHP怎么学才快?不用担心,这里为大家提供了PHP速学教程(入门到精通),有需要的小伙伴保存下载就能学习啦!

下载

相关标签:

node c#

本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

相关专题

更多
java break和continue
java break和continue

本专题整合了java break和continue的区别相关内容,阅读专题下面的文章了解更多详细内容。

2025.10.24

867

6

string转int
string转int

在编程中,我们经常会遇到需要将字符串(str)转换为整数(int)的情况。这可能是因为我们需要对字符串进行数值计算,或者需要将用户输入的字符串转换为整数进行处理。php中文网给大家带来了相关的教程以及文章,欢迎大家前来学习阅读。

2023.08.02

7639

3

int占多少字节
int占多少字节

int占4个字节,意味着一个int变量可以存储范围在-2,147,483,648到2,147,483,647之间的整数值,在某些情况下也可能是2个字节或8个字节,int是一种常用的数据类型,用于表示整数,需要根据具体情况选择合适的数据类型,以确保程序的正确性和性能。本专题为大家提供相关的文章、下载、课程内容,供大家免费下载体验。

2024.08.29

3625

6

c++怎么把double转成int
c++怎么把double转成int

本专题整合了 c++ double相关教程,阅读专题下面的文章了解更多详细内容。

2025.08.29

4768

10

C++中int的含义
C++中int的含义

本专题整合了C++中int相关内容,阅读专题下面的文章了解更多详细内容。

2025.08.29

3185

10

堆和栈的区别
堆和栈的区别

堆和栈的区别:1、内存分配方式不同;2、大小不同;3、数据访问方式不同;4、数据的生命周期。本专题为大家提供堆和栈的区别的相关的文章、下载、课程内容,供大家免费下载体验。

2023.07.18

7127

5

堆和栈区别
堆和栈区别

堆(Heap)和栈(Stack)是计算机中两种常见的内存分配机制。它们在内存管理的方式、分配方式以及使用场景上有很大的区别。本文将详细介绍堆和栈的特点、区别以及各自的使用场景。php中文网给大家带来了相关的教程以及文章欢迎大家前来学习阅读。

2023.08.10

2908

6

页面置换算法
页面置换算法

页面置换算法是操作系统中用来决定在内存中哪些页面应该被换出以便为新的页面提供空间的算法。本专题为大家提供页面置换算法的相关文章,大家可以免费体验。

2023.08.14

7216

4

热门下载

更多
网站特效
/
网站源码
/
网站素材
/
前端模板

精品课程

更多
相关推荐
/
热门推荐
/
最新课程
WebSocket手册
WebSocket手册

共0课时 | 0人学习

HTML5/CSS3/JavaScript/ES6入门课程
HTML5/CSS3/JavaScript/ES6入门课程

共102课时 | 11.2万人学习

前端基础到实战(HTML5+CSS3+ES6+NPM)
前端基础到实战(HTML5+CSS3+ES6+NPM)

共162课时 | 29.2万人学习