计算机网络基础 (十)--- 网络层 - 迪杰斯特拉算法

关注

发布于: 2020 年 07 月 28 日

文章内容概览
﻿
迪杰斯特拉算法﻿
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到各个顶点的最短距离
﻿
在快速变化的技术中寻找不变，才是一个技术人的核心竞争力。知行合一，理论结合实践
﻿