文件名称:Floyd算法求点与点之间的最短路径
文件大小:1KB
文件格式:TXT
更新时间:2013-11-10 13:16:25
Floyd算法 最短路径
给出一个带权有向图G=(V,E),其中每一条边(v,w)的权c[v,w]是一个非负实数。要求对任意的顶点有序对(v,w)找出从顶点v到顶点w的最短路径长度。这个问题就称为带权有向图的所有顶点对之间的最短路径问题。解决这个问题的一个办法是,每次以一个顶点为源,重复执行Dijkstra算法n法。这样,就可以求得所有顶点对之间的最短路径。这样做所需要的计算时间为O(n^3)。另外,也可以采用的较直接的Floyd算法。