你的位置:主页 > 皇冠体育手机版 >

用MATLAB写dijkstra算法(求简单的最短路问题)

2020-07-20 | 人围观

  在MATLAB里面,我们用邻接矩阵来表示一个有向图之间的节点与节点之间的距离。

  假如我们现在有六个节点,他们之间的距离如下表所示:

  0

  50

  ∞

  40

  25

  10

  50

  0

  15

  20

  ∞

  25

  ∞

  15

  0

  10

  20

  ∞

  40

  20

  10

  0

  10

  25

  25

  ∞

  20

  10

  0

  55

  10

  25

  ∞

  25

  55

  0

  下面先写个Dijkstra算法的文件,方便之后直接调用:

  代码的输入是:

  邻接矩阵

  起点

  终点

  代码注释的很详细,可以步进看一下具体怎么操作的。

  其实就是,比如我们算1-3的距离,首先找出来的是1到那个点最近,然后再从那个点出发再去找最近的点。distance数组存放的是这个起点到这个节点的最近距离,所以这样就保证了该节点位置上的值一定是最短的路径值。parent数组存放的是当前这个角标位置的父节点,如果这个父节点不为空 ,那么这个就一定存在路径。

  下面用上面那个表格的数据来测试:

  输出为:

  昨天开始用MATLAB写代码,不当之处欢迎大佬多多指点

标签:
Top