1.软件版本

matlab2022a

2.运行方法

     使用matlab2022a或者高版本仿真，运行文件夹中的tops.m或者main.m。运行时注意matlab左侧的当前文件夹窗口必须是当前工程所在路径。具体操作观看提供的程序操作视频跟着操作。

3.部分仿真截图

4.内容简介

    Dijkstra（迪杰斯特拉）算法是典型的最短路径路由算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止（BFS、prime算法都有类似思想）。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。

算法描述

（1）S为已经找到的从v出发的最短路径的终点集合，它的初始状态为空集，将源点加入S中。 其余顶点构成集合U。

（2）构建源点到其余顶点的距离列表，与源点不相连的顶点距离记为∞。

（3）广度遍历与源点相连的顶点，找到距离最近的顶点，则到这个顶点的最短路径就确定了，最短距离就是当前距离，将这个顶点从U中拿出，放入S中。

（4）用当前的顶点作为中间点，对其进行广度遍历，对遍历到的顶点距离进行更新。

（5）在U中搜索最短距离的顶点，将其放入S。

（6）以这个节点作为中间点广度搜索，更新距离。

（7）重复这个过程，直至U为空。