7.6 最短路径

01

前言

1、假若要在计算机上建立一个交通资讯系统则可以采用图的结构来表示实际的交通网络。

2、考虑到交通图的有向行（如航运，逆水和顺水时的船速就不一样）带权有向图中，称路径上的第一个顶点为源点，最后一个顶点为终点。

02

最短路径

1、求最短路径的一个办法是，每次以一个顶点为源点，重复执行迪杰斯特拉算法n次。这样，便可求得每一对顶点之间的最短路径。总的执行时间为O（n的3次方）。

2、弗洛依德算法：通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。 从图的带权邻接矩阵A=[a(i,j)] n×n开始，递归地进行n次更新，即由矩阵D(0)=A，按一个公式，构造出矩阵D(1)；又用同样地公式由D(1)构造出D(2)；……；最后又用同样的公式由D(n-1)构造出矩阵D(n)。矩阵D(n)的i行j列元素便是i号顶点到j号顶点的最短路径长度，称D(n)为图的距离矩阵，同时还可引入一个后继节点矩阵path来记录两点间的最短路径。采用松弛技术（松弛操作），对在i和j之间的所有其他点进行一次松弛。所以时间复杂度为O(n^

如果您觉得本篇文章对您有作用，请转发给更多的人，点一下好看就是对小编的最大支持！