算法导论之每对顶点间的最短路径

从单源顶点最短路径到每对顶点间最短路径，求解的问题从一个点扩展到所有点，描述如下：给定一个加权有向图G=(V,E)，其加权函数w:E->R为边到实数权值的映射，对于每对顶点u,v∈V，找出从u到v的一条最短路径，其中路径的权值是指其组成边的权值之和。可以把单源最短路径算法运行|V|次来解决每对顶点间最短路径问题，每一次运行时，每个顶点轮流作为源顶点。用邻接表表示的话，输出第u行第v列的元素就是从u到v的最短路径的权值。

从点计算衍生到多点计算，矩阵无疑是最好的形式化工具。假设顶点编号从1,2,…,|V|，输入一个nXn的矩阵W，矩阵中点就是边，一般算法允许存在负权的边，但不能存在负权回路；输出一个nXn的矩阵D=(d_ij)，d_ij是从i到j的最短路径的权值。如果用表示从顶点i到顶点j的最短路径的权值，在算

总结

以上是生活随笔为你收集整理的算法导论之每对顶点间的最短路径的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。