Java实现几种八上数学最短路径问题题

来源：蜘蛛抓取(WebSpider) 时间：2018-05-26 18:45 标签： 八上数学最短路径问题

最近遇到一个问题求最短路径嘚算法（flody，dijktra）只能计算出节点A-B之间的一条最短路径

如果A-B之间存在两条最短路径，则只寻找一条那位高手帮忙怎么计算出多个最短路径並记录。

　　以起始点为中心向外层层扩展直到扩展到终点为止。

　　1.构建二维数组weight存储无向图weight[i][j]表示节点i到节点j的权值，即节点i到节点j的距离(下文以dij表示)

　　  3.构建数组visited，标記各节点是否已被扩展（假设0为为扩展1为已扩展），初始化visited[0] = 1,其他值为零

　　  4.迭代算法，遍历二维数组weight选择离起始节点距离最短的未標记结点k，将d0k记录至shortpath并将k标记为已扩展，

//选择一个离起始点最近的未标记顶点且到起始点的最短路径为dmin //以k为中间点，更新起始点到其怹未标记各点的距离

起始点到1的最短路径为:0->1距离为：50

算法只要懂原理了代码都是小問题，先看下面理论尤其是红色标注的（要源码请留下邮箱，有测试用例直接运行即可）

是一种静态路网中求解最短路最有效的直接搜索方法。

其中 f(n) 是从初始点经由节点n到目标点的估价函数

中从初始节点到n节点的实际代价，

h(n) 是从n到目标节点最佳路径的估计代价

（最優解的）条件，关键在于估价函数f(n)的选取：

的距离实际值这种情况下，搜索的点数多搜索范围大，效率低但能得到最优解。并且如果h(n)=d(n)即距离估计h(n)等于最短距离，那么搜索将严格沿着最短路径进行 此时的搜索效率是最高的。

如果 估价值>实际值,

的点数少搜索范围小，效率高但不能保证得到最优解。

/* 循环次数为了防止目标不可到达 */ * 获取点1到点1的最佳路径 * 把该节点相邻点加入打开的列表 * 把该节点相鄰点加入关闭的列表 * 当前点到该点的消耗

* 求点1到点2的合适路线

我要回帖

更多关于 八上数学最短路径问题 的文章

 

随机推荐