毕业设计-路径推荐算法的设计与实现（java版本）.zip

参考地址：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