Dijkstra算法与matlab结果解读

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了Dijkstra算法与matlab结果解读，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1721字，纯文字阅读大概需要3分钟。

内容图文

图论 Dijkstra算法与matlab结果解读

可以求出图G中从顶点开始到其余各个顶点的最短路。

在这里不列出复杂的数学公式，只对其原理和使用方式做叙述

原理

Dijkstra算法能够求出顶点到其余各个顶点的最短路径。属于贪心算数

1.首先，选取起点，历经顶点周围的所有路径，先找到最短（权重最小）的一条路，当确定了这条后。

2.历经顶点1，顶点2周围的所有路径，找到下一个到原点最短的点（计算以顶点2为中转点，到各个点的距离和从原点直接出发到各个点的距离，选择到顶点最短路）例如：若A—B的距离小于A—C—B，则第三个点选择B边选择A—B

3.现在已经确定两个定点到所选原点的最短路径了，接下来依次执行2，最终得到一条连通树，虽然树上有不同的分支，但树上的每个定点到原点的路仅有一条（即是最短路）

一篇非常好的图文讲解：https://blog.csdn.net/u013414501/article/details/50506907

上图即求出各个点到原点的最短路径

matlab实现及结果解读

例：
2. 某企业使用一台设备，在每年年初，企业领导部门就要购置新的，还是继续使用旧的。若购置新设备，就要支付一定的购置费用；若继续使用旧设备，则需支付更多的维修费用。现在的问题是如何制定一个几年之内的设备更新计划，使得总的支付被费用最少。以一个五年之内更新某种设备的计划为例，若已知该种设备在各年年初的价格如表1所例，还已知使用不同时间（年）的设备所需要的维修费用用如表2所例。如何制定使得总的支付费用最少的设备更新计划呢？

首先列出邻接矩阵

从而将总费用最少的设备更新计划问题，归结为求图G中从v1到v6的最短路径问题，可以使用Dijkstra标号算法求解。

clc;clear

a=zeros(6);%邻接矩阵初始化

a（1，[2:6]）=[16 22 30 41 61];%输入邻接矩阵，注意这里为有向图

a（2，[3:6]）=[16 22 30 41];

a（3，[4:6]）=[ 17 23 31];

a（4，[5:6]）=[17 23];

a（5，6）=18;

b=sparse(a);%有向图直接变成稀疏矩阵就可以了。

[dist,path]=grapshorttestpah(b,1,6,’Directed’,1)%调用工具箱求最短路

结果

dist = 53
path = 1×3
     1     3     6

结果解读：从节点1到节点的最短路径为1—3—6，最短路程为53

内容总结

以上是互联网集市为您收集整理的Dijkstra算法与matlab结果解读全部内容，希望文章能够帮你解决Dijkstra算法与matlab结果解读所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---