小网站关键词,公司网站怎么做网站备案,自己创建网站容易吗,wordpress企业类模板下载这里使用Dijkstra(戴克斯特拉)算法#xff0c;该算法起始点实际计算出到任一点的距离#xff0c;计算两城市间的距离实际是一个副产物#xff0c;所有一下图为例来说明#xff0c;该图为无向图#xff0c;顶点间所标数字即为两点之间的距离。 问题#xff1a;求点D到点A的… 这里使用Dijkstra(戴克斯特拉)算法该算法起始点实际计算出到任一点的距离计算两城市间的距离实际是一个副产物所有一下图为例来说明该图为无向图顶点间所标数字即为两点之间的距离。 问题求点D到点A的距离。 初始状态 集合S中 D(0)D到D的距离为0 集合U中 A(∞)D不能直接到达AB(∞) D不能直接到达BC(3)D直接到达C的距离为3E(4)D直接到达E的距离为4F(∞)D不能直接到达FG(∞)D不能直接到达G。 第1步由初始条件可以看出U集合中C到D的距离最小故将C添加到集合S中更新后两集合关系如下 D到C的最小距离为3D到C的路线为 第2步逐个判断集合S中元素到集合U中的距离并将距离最小的点添加到集合S中 对A点 对B点 对E点: 对F点: 对G点: 由上可以看出 距离最小为4将E添加到集合S中更新后的集合如下 更新后D到E的最短距离4D到E的最短路线为 第3步逐个判断集合S中元素到集合U中的距离并将距离最小的点添加到集合S中 对A点 对B点 对F点 对G点 由上可以看出距离最小为6故将F点加入到S集合中更新后S和U分别为 跟新后D到F的最短距离为6最短路线为 第4步逐个判断集合S中元素到集合U中的距离并将距离最小的点添加到集合S中 对A点 对B点 对G点 由上可以看出距离最小为12故将G点加入到S集合中更新后S和U分别为 更新后D到G的距离最短12最短路线 第5步逐个判断集合S中元素到集合U中的距离并将距离最小的点添加到集合S中 对A点 对B点 由上可以看出或距离最小为13故将G点加入到S集合中更新后S和U分别为 更新后D到B的最短路线为13D到B最短路线为 或 第6步逐个判断集合S中元素到集合U中的距离并将距离最小的点添加到集合S中 对A点(D到B的最短路线有2条我们可以任选一条这里选D→C→B) 由上可以看出 距离最小为22故将G点加入到S集合中更新后S和U分别为 更新后D到A的最短路线为22D到B最短路线为
