毕业论文移动版

    Floyd算法求解最短路径在一个正的或负的边权值的加权图的算法（但没有负周期）。一个执行的算法会发现长度所有顶点对之间的最短路径，虽然它并不会返回的路径本身的细节。版本的算法也可用于求一个关系的传递闭包，或（与该投票系统连接）宽的路径的所有顶点对之间的加权图中。

  2。3。1 Dijkstra算法和Floyd算法的原理

Dijkstra算法：

首先，我们需要引进一个辅助向量，此向量的每个分量都表示当前所找到的从始点到每个终点的最短路径的长度。如表示从始点到终点3的路径，它的相对最小长度是2。这里要强调的是所谓的相对就是说在算法过程中的值是一直在逼近最终结果而不是过程中的值就等于最短路径长度。它的起始状态为：若从到有弧，则为弧上的权值，否则置为。显然，从出发的长度的最短的一条路径就是长度为的路径，此路径为。那么，假设该次短路径的终点是，则这条路径不是是，就是。它的长度不是是从到的弧上的权值，就是是和从到的弧上的权值之和。通常假设为已求得最短路径的终点的集合，那么就可以证明：下一条寻找的最短路径（设其终点为）不是弧，就是中间只经过点而最后到达顶点的路径。所以，下一条次短的最短路径的长度必须为，其中要么是弧上的权值，要么是和弧上的权值之和。来.自^优+尔-论,文:网www.youerw.com +QQ752018766-

Floyd算法：

    Floyd算法同样也是经典的求最短路的算法。通俗地讲，就是首先我们要设定目标是寻找从点，之间的最短路。然后我们再从动态规划的角度看这个问题，就需要为了在这一目标做一个新的诠释（动态规划最有价值的精华就在于这个诠释）。

  两个任意点与之间的最短路径只有两种可能，一种是直接从到，另一种就是从同过若干个点再到。所以，我们有

定义2。3。1。1：为点到点的最短路径的距离。

对于每一个点，我们检查是否小于，如果小于的话，就证明了从同过若干个点再到的路径要比从直接到的路径更短，我们便设置，这样一来，当我们遍历完所有点，中记录的便是到的最短路径的距离。