实验原理
Dijkstra（狄克斯特拉）算法用于计算通信网中指定节点到其他各节点的最短路径，简称D算法。Dijkstra算法的大致思路是，先把距离初始节点最近的节点找到，加入置定节点集\(\rm{G_p}\)，再以这个节 点为基础寻找下一个节点，没找到一个节点都加入到置定节点集中，最终把初始节点到其他各个节点的最短距离依次找出。这里以节点1为初始节点说明：
- 构建一个距离（dis）列表，存入节点1到其他各个节点的距离。对于节点1不能直接到达的节点，则赋值为一个很大的数（比如999）代替；
- 从 dis 列表中，我们可以求得一个最小值，即是距离初始节点 1 最近的一个点，我们假设是节点 3。这也是从节点 1 到节点 3 的最短路径，因为无论从初始节点经过别的任何节点再到节点 3 的距离肯定大于这个最小值，这时把节点3存入置定节点集\(\rm{G_p}\);
- 接下来更新 dis 列表，即比较初始节点 1 到其它各个节点的距离与节点 1 经过节点 3 再到其它节点的距离，保存较小的那一个值存入 dis 列表。再找出新的 dis 列表里面，除了确定点之外的最小的值，即是下一个要确定的点;
- 依次执行上述步骤，直到每一个点都确定，此时 dis 列表中所存的数据既 是初始节点到其它各个节点的最短距离。
实验仿真
通过Python实现Dijkstra算法的函数Dijkstra (D, begin, end)，其中：
- D为输入的无向图节点间路径长度矩阵；
- begin为起始节点；
- end为目标节点。
例题中的无向图有6个节点，如下图所示：
根据无向图可以得到节点间的距离矩阵可表示为：
\[\left[\begin{array}{cccccc}
0 & 7 & 1 & \infty & \infty & 6 \7 & 0 & 5 & \infty & 6 & \infty \1 & 5 & 0 & 2 & \infty & 10 \\infty & \infty & 2 & 0 & 8 & 9 \\infty & 6 & \infty & 8 & 0 & 5 \6 & \infty & 10 & 9 & 5 & 0
\end{array}\right]
\]
假定初始节点为节点1，目标节点为节点5，则最短路径以及径长的仿真结果如下所示：
通信网实验—Dijkstra算法
原文：https://www.cnblogs.com/MayeZhang/p/13998372.html
