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之间的所有其他点进行一次松弛。
更多案例可以go公众号：C语言入门到精通
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读