关于计算机网络:计算机网络基础十网络层迪杰斯特拉算法

41次阅读

共计 1251 个字符，预计需要花费 4 分钟才能阅读完成。

文章内容概览

Dijkstra（迪杰斯特拉）算法是驰名的图论算法
Dijkstra 算法解决有权图从一个节点到其它节点的 最短门路 问题
特点：“以终点为核心，向外层层扩大”

假如有下图这样的一个网络，该网络有 A、B、C、D、E、F 这几个节点和若干条边，每条边都有相应的间隔。假如此时要求 A 到 E 的最短门路

下边列出由 A 到 E 的所有可能的门路以及门路长度

A->B->C->E = 13
A->C->E = 11
A->D->C->E =13
A->D->E = 9
A->F->E = 10

从列出的后果来看，最短的门路是 A ->D->E 这条，间隔是 9。这是人为的去查找的，然而咱们是须要将其转换成程序语言来解决求最短门路问题

先用文字介绍一下该算法的整个过程，而后再通过例子来解释每个过程

迪杰斯特拉算法过程形容

初始化两个汇合(S,U)（S 为只有初始顶点点 A 的汇合，U 为其它顶点的汇合）
如果 U 不为空，对 U 汇合顶点进行间隔的排序，并取出间隔 A 最近的一个顶点 D

将顶点 D 放入 S 汇合
更新通过顶点 D 达到 U 汇合所有点的间隔（如果间隔更小则更新，否则不更新）
反复步骤 2

直到 U 汇合为空，整个算法过程实现

通过下边的例子来了解上边的过程

因为要求 A 到 E 的最短距离，所以，首先将 A 纳入 S 汇合，且 A 到 A 的间隔为 0。而后其它顶点 U 的汇合就是 B、C、D、E、F，并计算 A 到这几个顶点的间隔，从图中能够看进去

因为汇合 U 不为空，所以对汇合 U 中，A 到各个顶点的间隔进行排序，找到到 A 的间隔最短的顶点，将其放入汇合 S。从图中能够看进去，A 到顶点 B 的间隔是最小的，所以将其放入汇合 S

而后应该计算： A 通过 B 达到其余各个顶点的间隔

因为晓得 B 到 C 的间隔为 5，所以 A 通过 B 达到 C 的间隔为：A->B->C = 6+5 = 11，因为原来汇合 U 中 A 到 C 的间隔为 9，9 < 11，所以，不须要更新到汇合 U 中，而后就失去下边这样的后果

而后再对 U 进行判断，发现不为空。所以对 U 中 A 到各个顶点的间隔再进行排序，发现 A 到 F 的间隔是最短的，此时就把到 F 放入到 S 汇合中。而后此时计算 A 通过 F 达到各个顶点的间隔。发现 A 通过 F 达到 E 的间隔为 10，此时，更新 U 中 A 到顶点 E 的间隔（原来这个间隔是不晓得的），然就失去如下后果

而后就是反复上边的步骤，发现 U 中距离最短的是 D，那么就把 D 放入到汇合 S，而后计算 A 通过 D 达到各个顶点的间隔，发现 A 通过 D 达到 C 的间隔为 11，A 通过 D 达到 E 的间隔是 9。此时发现 A 通过 D 达到 C 的间隔大于 U 中的 A 到 C 的间隔 9，所以不替换 U 中 A 到 C 的间隔。而后发现 A 通过 D 达到 E 的间隔 9，小于 U 中 A 到 E 的间隔 10，所以，替换掉 U 中 A 到 E 的值，那么就失去如下后果

而后汇合 U 中还剩两个元素（两个间隔值雷同，轻易选一个放入汇合 S），接着反复上边的步骤，直到汇合 U 为空。最终失去如下后果

失去的 S 汇合中的间隔就是 A 达到各个顶点的最短距离，以上便是迪杰斯特拉算法的整个过程。有趣味的话也能够推一个 B 到各个顶点的最短距离

在疾速变动的技术中寻找不变，才是一个技术人的外围竞争力。知行合一，实践联合实际

正文完