博客
关于我
图的Dijkstra算法(最短路径)
阅读量:641 次
发布时间:2019-03-14

本文共 509 字,大约阅读时间需要 1 分钟。

迪杰斯特拉算法的步骤如下:

  • 初始化:将起始节点v1的距离设为0,并将其加入优先队列。

  • 处理节点v1:从队列中取出v1,查看它的所有直接邻居节点,包括v6、v5和v3。初始化这些邻居节点v3、v5、v6的距离分别为各自边的权重。例如:

    • v3:距离10
    • v5:距离30
    • v6:距离100
  • 更新优先队列:将邻居节点加入优先队列,并标记为已访问。

  • 处理节点v3:取出v3,检查其所有邻居节点,如v2和v4。计算这些节点通过v3的距离,更新它们的最短距离:

    • v2:距离10 + 5 = 15
    • v4:距离10 + 50 = 60
  • 处理节点v5:取出v5,检查其邻居节点,发现没有未被处理的更短路径,因此不进行更新。

  • 处理节点v6:取出v6,检查其邻居节点,如未知其他节点,无需更新。

  • 处理节点v2:取出v2,无未连接节点,无需更新。

  • 处理节点v4:取出v4,检查其邻居节点,发现是否有通过v4更短的路径,若有,更新相应节点的距离。

  • 处理剩余节点:继续处理队列,算法完成。

  • 通过以上步骤,得到各节点的最短路径:

    • v1到v3的距离为10
    • v1到v2的距离为15
    • v1到v4的距离为60
    • v1到v5的距离为30
    • v1到v6的距离为100

    转载地址:http://oaulz.baihongyu.com/

    你可能感兴趣的文章
    Objective-C实现combine Without Repetitions不重复地结合算法(附完整源码)
    查看>>
    Objective-C实现conjugate gradient共轭梯度算法(附完整源码)
    查看>>
    Objective-C实现connected components连通分量算法(附完整源码)
    查看>>
    Objective-C实现Convex hull凸包问题算法(附完整源码)
    查看>>
    Objective-C实现convolution neural network卷积神经网络算法(附完整源码)
    查看>>
    Objective-C实现coulombs law库仑定律算法(附完整源码)
    查看>>
    Objective-C实现currency converter货币换算算法(附完整源码)
    查看>>
    Objective-C实现cycle sort循环排序算法(附完整源码)
    查看>>
    Objective-C实现data transformations数据转换算法(附完整源码)
    查看>>
    Objective-C实现DBSCAN聚类算法(附完整源码)
    查看>>
    Objective-C实现DBSCAN聚类算法(附完整源码)
    查看>>
    Objective-C实现degreeToRadian度到弧度算法(附完整源码)
    查看>>
    Objective-C实现depth first search深度优先搜索算法(附完整源码)
    查看>>
    Objective-C实现des文件加密算法(附完整源码)
    查看>>
    Objective-C实现deutsch jozsa算法(附完整源码)
    查看>>
    Objective-C实现DFS判断是否是二分图Bipartite算法(附完整源码)
    查看>>
    Objective-C实现Diffie-Hellman算法(附完整源码)
    查看>>
    Objective-C实现Dijkstra最小路径算法(附完整源码)
    查看>>
    Objective-C实现dijkstra迪杰斯特拉算法(附完整源码)
    查看>>
    Objective-C实现Dijkstra迪杰斯特拉算法(附完整源码)
    查看>>