2) 弗洛伊德算法：
方法：两条线，从左上角开始计算一直到右下角 如下所示：
给出矩阵，其中矩阵A是邻接矩阵，而矩阵Path记录u,v两点之间最短路径所必须经过的点。
最后A3即为所求结果。
第9章、查找
1. 查找表：是由同一类型的数据元素（或记录）构成的集合。
2. 关键字：是数据元素（或记录）中某个数据项的值，用它可以标识（识别）一个数据元素（或记录）。
3. 静态查找表：查询某个特定的数据元素是否在查找表中，检索某个特定的数据元素的各种属性。
1) 顺序查找法：从表中最后一个记录开始，逐个进行记录的关键字和给定值比较，若某个记录的关键字和给定值比较相等，则查找成功，找到所查记录；反之若直至第一个记录，其关键字和给定值比较都不相等，则表明表中没有所查记录，查找不成功。
其存储结构要求：以顺序表或线性链表表示的静态查找表。
其平均查找长度：假设每个记录的查找概率相等，即Pi=1/n，则在等概率情况下顺序查找的平均查找长度为，ASL=(n+1)/2。 2) 折半查找法（二分查找法）：先确定待查记录所在的范围（区间），然后逐步缩小范围直到找到或找不到该记录为止。
其存储结构要求：以有序表表示的静态查找表。
其平均查找长度：假设表中每个记录的查找概率相等（Pi=1/n），则查找成功时折半查找的平均查找长度为，ASL=(n+1)/n*log2(n+1)-1。 3) 索引顺序表查找法（分块查找法）：先确定待查记录所在的块（子表），然后在块中顺序查找。
其存储结构要求：以索引顺序表表示的静态查找表。
其平均查找长度：将长度为n的表均匀地分成b块，每块含有s个记录，即b=[n/s]；又假设表中每个记录的查找概率相等，则每块查找概率为1/b，块中每个记录的查找概率为1/s，若用顺序查找确定所在块，则分块查找的平均查找长度为，ASL=(n/s+s)/2+1；若用折半查找确定所在块，则分块查找的平均查找长度为，ASL≈log2(n/s+1)+s/2。
4. 动态查找表：在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已存在的某个数据元素。
1) 二叉排序树：或者是一棵空树；或者是具有下列性质的二叉树：1、若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；2、若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；3、它的左、右子树也分别为二叉排序树。
2) 平衡二叉树（AVL树）：它或者是一棵空树；或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。若将二叉树上结点的平衡因子BF定义为该结点的左子树的深度减去它的右子树的深度，则平衡二叉树上所有结点的平衡因子只可能是 -1、0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。
下面即四种情况分别为：左左、右右、左右、右左，每种情况又有两个图①、②，①是该情况的最简单的图形，②是该情况的一般的图形。 设x为最小不平衡子树的根结点，y为刚插入的点 左左：即在x的左孩子a的左孩子c上插入一个结点y（该结点也可以是c,如图①），即y可以是c，也可以是c的左孩子（如图②），也可以是c的右孩子（不在画出）。
图①就不用说了，结点x和结点a变换，则树平衡了；那么图②就是树中的一般情况了a结点有右孩子d，那要进行x和a变换，那么a的右孩子放哪啊？很简单，如图放在x的左孩子上；分析：x>d,d>a,所以d可作为x的左孩子，且可作为a的右孩子中的孩子。下边这样的类似情况不再一一分析，自己分析分析~ 实现：找到根结点x，与它的左孩子a进行交换即可使二叉树树再次平衡；