参考地址:https://blog.csdn.net/qq_34842671/article/details/90083037
1.为什么迪杰斯特拉算法只支持非负权的图?
迪杰斯特拉采用的贪心策略,S集合中是已经计算出最短路径的节点,T集合中是未计算出最短路径的节点。假设存在负权,源点为A,
已经计算出A->B的最短路径为m,若下一次将C添加进已计算出最短路径的节点集合,而A->C=m,C->B=-1,则会出现A->B的更短路径A->C->B,
但迪杰斯特拉不会对已经计算出最短路径的节点重新计算,因此无法更新最短路径,即负权的出现导致无法保证S中节点计算的是最短路径,
已经固定dis的点可能会被其它dis大于它的点更新。
2.为什么在代码实现中不能将节点之间不可达用Integer.MAX_VALUE代表?
因为两个Integer.MAX_VALUE相加会溢出导致出现负权,所以最好设置为一个比较大且不容易相加溢出的数。
3.迪杰斯特拉算法适用于什么场景?
在有些算法书上说,迪杰斯特拉适用于DAG(有向无环图)。但是个人觉得,它所谓的“适用于”,或许只是说可以在DAG上使用,并不代表无向图不能使用,
也不能代表有环图不能使用。从迪杰斯特拉的算法原理上来说,无向图是没有问题的,只需要给matrix[source][target]和matrix[target][source]
赋上相同的权值,因为它每次只会根据到源点的距离,选取距离最近的一个节点加入,所以有没有方向都无所谓,算法只关注可达点的距离;至于有环图,
它对每个节点的距离计算只用了一层遍历去做,并不会陷入死循环,也不会出现重复计算的问题。因此迪杰斯特拉算法是可以用在无向图和有环图中的,
适合于求单源最短路径。
样例输入:
7 10
0 1 6
1 2 5
0 3 2
3 1 7
3 4 5
1 2 5
1 5 3
4 5 5
5 4 2
4 6 1
0
没有合适的资源?快使用搜索试试~ 我知道了~
温馨提示
【资源说明】 1、该资源包括项目的全部源码,下载可以直接使用! 2、本项目适合作为计算机、数学、电子信息等专业的课程设计、期末大作业和毕设项目,作为参考资料学习借鉴。 3、本资源作为“参考资料”如果需要实现其他功能,需要能看懂代码,并且热爱钻研,自行调试。 基于java的路径推荐算法的设计与实现源码(毕业设计).zip
资源推荐
资源详情
资源评论
收起资源包目录
基于java的路径推荐算法的设计与实现源码(毕业设计).zip (19个子文件)
code_20105
src
com
java
floyd
ponder.txt 654B
Floyd.java 2KB
aStar
ponder.txt 225B
AStar.java 48B
TestClass.java 175B
dijkstra
Dijkstra.java 3KB
ponder.txt 1KB
graduation_project_Path_recommendation_algorithm.iml 793B
out
production
graduation_project_Path_recommendation_algorithm
com
java
floyd
ponder 654B
Floyd.class 3KB
TestClass.class 542B
dijkstra
ponder.txt 1KB
Dijkstra.class 2KB
.idea
$PRODUCT_WORKSPACE_FILE$ 489B
vcs.xml 180B
misc.xml 273B
modules.xml 336B
.gitignore 38B
encodings.xml 334B
共 19 条
- 1
资源评论
土豆片片
- 粉丝: 1556
- 资源: 5641
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功