第六章图的学习感觉比较侧重阅读和理解代码，而写代码部分占比比较小。所以这一章的总结全都是知识点的整理，是用自己的话来表达自己对代码以及做题过程步骤的理解。邻接表存储顶点名称，同时将顶点下标存储在一个结点内，因此当邻接矩阵调用Locate方法来得到顶点下标值

迪杰斯特拉算法用于计算一个节点到其他所有节点的最短路径。准备2个集合 S 和 U. S保存已经计算好的源节点到此节点最短距离。每次从U中取出最小的值，放入S中，其他节点根据此节点重写计算最短距离。U={A(无穷大),B(无穷大),C,E,F(无穷大),G(

SPFA算法，是西南交通大学段凡丁于 1994 年发表的，其在 Bellman-ford 算法的基础上加上一个队列优化，减少了冗余的松弛操作，是一种高效的最短路算法。这样不断从队列中取出顶点来进行松弛操作，直至队列空为止。（所谓的松弛操作，简单来说，对于顶

private int [][]graph;private int size;private int[][] d;private int[][] n;this.graph = graph;size=graph.length;d=new int[size][

1) 和 Dijkstra 算法一样，弗洛伊德算法也是一种用于寻找给定的加权图中顶点间最短路径的算法。该算法名称以创始人之一、1978 年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。2) 至于 vi 到 vk 的最短路径 Lik 或者 v

可以求出多源最短路，可以处理负权边的情况，但是不能出现负环。Floyed算法使用的是动态规划的方法。我们首先观察上图。所以如果同时经过1号和2号两个城市中转的话，从4号城市到3号城市的路程会进一步缩短为10。好，下面我们将这个问题一般化。当任意两点之间不允

由于蚁群算法涉及到的参数蛮多的，且这些参数的选择对程序又都有一定的影响，所以选择合适的参数组合很重要。蚁群算法有个特点就是在寻优的过程中，带有一定的随机性，这种随机性主要体现在出发点的选择上。蚁群算法正是通过这个初始点的选择将全局寻优慢慢转化为局部寻优的。

用于解决单源最短路径的问题，但也能够处理有负权边的情况。这是与Djikstra算法不同的地方。关于复杂度，要比Djikstra的复杂度更高一点。原理，就是会出现负环的情况，会使得最短路径越来越小，进而产生错误；如果出现负环，源点无法到达，那么也是不会影响求

继续复习数据结构和算法，总结一下求解最短路径的一些算法。核心代码如下，图存储在邻接矩阵G中。代码如下，nowIndex代表当前源点编号，minDis是当前源点到其他点的最短距离，用于选择下一个源点，dis数组存储每个点到最终目标点的距离，也就是结果，mar

全局最短路径实际是计算每个源点到其他各个顶点的最短路径的长度，我们可以调用dijkstra算法N次，常见解决全局最短路径的方法是Floyd-Warshall算法，但是Floyd-Warshall算法不能解决负边问题。为了解决负边问题，我们使用Bellman

链路是路由器接口的另一种说法，因此OSPF也称为接口状态路由协议。OSPF通过路由器之间通告网络接口的状态来建立链路状态数据库，生成最短路径树，每个OSPF路由器使用这些最短路径构造路由表。OSPF路由协议用于在单一自治系统内决策路由。在这里，路由域是是指

由于我之前一直强调数据结构以及算法学习的重要性，所以就有一些读者经常问我，数据结构与算法应该要学习到哪个程度呢？这些算法与数据结构的学习大多数是零散的，并没有一本把他们全部覆盖的书籍。下面是我觉得值得学习的一些算法以及数据结构，当然，我也会整理一些看过不错

首先将起始位置A加入永久集合，并将A的距离设为0， 此时遍历A的邻接节点[B,C,E]，找到其距离A最短的节点B，将B插入到永久集合中，并更新B的距离为10，B的前驱节点为A。先放这，自己有点懵。

2019 年阿里巴巴 双11 核心系统 100% 以云原生的方式上云，完美支撑了 54.4w 峰值流量以及 2684 亿的成交量。随着阿里巴巴经济体云原生技术的全面升级，容器性能、稳定性及在线率也得到了全面提升。本文作者将从云计算时代容器的发展路径为出发点

此外，给定V中的一个顶点，称为源点。现在要计算从源点到所有其他各顶点的最短路径长度，这里路径长度指路上各边的权之和。　　算法基本思想：先假定源点为u，顶点集合V被划分为两部分：集合V以及集合V-S。初始时S中仅含有u,其中S的顶点到源点的最短路径已经确定。

Dijistra算法作为一种最短路径算法，可以用来计算一个节点到图上其他节点的最短距离。主要是通过启发式的思想，由中心节点层层向外拓展，直到找到中点。适用于无向图和有向图。引入两个集合（S，U），其中集合S表示已经求出最短路径的点，集合U表示还未求出最短路

if//如果这条边的终点到源点的距离大于起点到源点距离，就替换。中间关于“k”的部分，只是一种优化，可以删去，不影响算法。所以需要一个vis数组进行判断是否在队列中。

Dijkstra算法使用了广度优先搜索解决赋权有向图或无向图的单源最短路径问题输入：有权重的图G，起点S，V是途中顶点集合，E是图中所有顶点的集合。这条路径的长度是 d[u] + w。算法维护两个顶点集合S和Q。集合S初始状态为空，而后每一步都有一个顶点从

Dijkstra算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，

下面是一些比较重要的算法，原文罗列了32个，但我觉得有很多是数论里的，和计算机的不相干，所以没有选取。下面的这些，有的我们经常在用，有的基本不用。有的很常见，有的很偏。不过了解一下也是好事。也欢迎你留下你觉得有意义的算法。数据压缩是通过减少计算机中所存储数