最短路径弗洛伊德算法

1. floyd算法能不能保证有最优解

Floyd算法又称为弗洛伊德算法，插点法，是一种用于寻找给定的加权图中顶点间最短路径的算法。

算法过程:

把图用邻接距阵G表示出来，如果从Vi到Vj有路可达，则G[i,j]=d，d表示该路的长度；否则G[i,j]=空值。

定义一个距阵D用来记录所插入点的信息，D[i,j]表示从Vi到Vj需要经过的点，初始化D[i,j]=j。
把各个顶点插入图中，比较插点后的距离与原来的距离，G[i,j] = min( G[i,j], G[i,k]+G[k,j] )，如果G[i,j]的值变小，则D[i,j]=k。

在G中包含有两点之间最短道路的信息，而在D中则包含了最短通路径的信息。
比如，要寻找从V5到V1的路径。根据D，假如D(5,1)=3则说明从V5到V1经过V3，路径为{V5,V3,V1}，如果D(5,3)=3，说明V5与V3直接相连，如果D(3,1)=1，说明V3与V1直接相连。

2. floyd算法求最短路径

Floyd算法适用于APSP(AllPairsShortestPaths)，是一种动态规划算法，稠密图效果最佳，边权可正可负。此算法简单有效，由于三重循环结构紧凑，对于稠密图，效率要高于执行|V|次Dijkstra算法。

优点：容易理解，可以算出任意两个节点之间的最短距离，代码编写简单

缺点：时间复杂度比较高，不适合计算大量数据。

时间复杂度:O(n^3)；空间复杂度:O(n^2)；

任意节点i到j的最短路径两种可能：

直接从i到j；
从i经过若干个节点k到j。
map（i，j）表示节点i到j最短路径的距离，对于每一个节点k，检查map（i，k）+map（k，j）小于map(i，j),如果成立，map（i，j） = map（i，k）+map（k，j）；遍历每个k，每次更新的是除第k行和第k列的数。

步骤：

第1步：初始化map矩阵。
矩阵中map[i][j]的距离为顶点i到顶点j的权值；

如果i和j不相邻，则map[i][j]=∞。

如果i==j，则map[i][j]=0;
第2步：以顶点A(假设是第1个顶点)为中介点，若a[i][j] > a[i][1]+a[1][j]，则设置a[i][j]=a[i][1]+a[1][j]。

3. 用弗洛伊德算法求最短路径

是地信的题吧，先给你说v1怎么求，
先找出v1能去的最近的点，为V2，
如果S1i>S12+S2i
修改V1到Vi的距离为S12+S2i
然后去掉V2，在其余的点中找距V1最近的，按上面的方法修改
最后得到V1与其他各点的最短距离
同样的方法求出到其他点的最短距离

4. 求弗洛伊德算法的详细解释~

floyd算法思想：1，构建一个邻接矩阵存储任意两点之间的权值如图D0.

2、例如求v1,v4之间的最短路径。先增加v2做中间顶点，D[1][4]=∞。if（D[1][4]>D[1][2]+D[2]4]）=6+4）D[1][4]=10;这样就可以了。

3、如不能在离得较远的两点(例v1,v9）直接得到上述可以满足if的中间点，则跟据你书本的代码可以先构建原点到中间点的最短路径，继而就可以求得vi,v9之间的最短路径

5. 弗洛伊德算法可以解决无向图最短路径么

可以的，弗洛伊德算法利用动态规划解决了无向图中任意两个点之间的最短路径，时间复杂度是O(n^3)，n是图中点个数
同时可以使用狄杰斯卡拉算法解决无向图的最短路径问题，他计算的是图中指定点到其余各点的最短路径，时间复杂度是O(n^2)

6. 为什么floyd算法可以计算负权值图的最短路径问题

弗洛伊德算法：Dis(i,j) =min(Dis(i,j), Dis(i,k) + Dis(k,j)).
我是这么理解的，Dis(i,k)或Dis(k,j)可以有一条边是负的，只要两者之和不是负的就行，因为两个和为负就会选取到这个组合，但是路径的结果不应该是负的。Dijkstra中S(已求出解)中的每一个点解即最短路径是已求出的,若存在负数路径,可能存在已求出的解不是最优解.

7. 【讨论】最短路径弗洛伊德算法的时间复杂度

那么你的意思是说四个循环全部都执行了的哦？否则就不是O(n4)。你看最后一个循环是需要判断进入的，也就是说，那个循环在最内层，本身次数就少，加上排除不合法条件，很少能执行到，根据算法思想，那么应该忽略常数级

8. floyd算法求最短路径怎么用

Dijkstra算法
1.定义概览
Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。注意该算法要求图中不存在负权边。
问题描述：在无向图 G=(V,E) 中，假设每条边 E[i] 的长度为 w[i]，找到由顶点 V0 到其余各点的最短路径。（单源最短路径）

2.算法描述
1)算法思想：设G=(V,E)是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径 , 就将加入到集合S中，直到全部顶点都加入到S中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。
2)算法步骤：
a.初始时，S只包含源点，即S＝{v}，v的距离为0。U包含除v外的其他顶点，即:U={其余顶点}，若v与U中顶点u有边，则<u,v>正常有权值，若u不是v的出边邻接点，则<u,v>权值为∞。
b.从U中选取一个距离v最小的顶点k，把k，加入S中（该选定的距离就是v到k的最短路径长度）。
c.以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权。
d.重复步骤b和c直到所有顶点都包含在S中。

9. Floyd算法除了能求出最短距离值外,还能求出最短路径吗它和Dijstra算法有什么区别

Floyd算法可以求出最短路径 但要求除了距离矩阵之外 还要保存一个结果矩阵 用结果矩阵还原出最短路

Floyd算法跟Dijstra算法最主要的区别在于 Floyd算法可以给出所有顶点间的最短路径 而Dijstra只能给出从一个特定顶点到其他顶点的最短路径 同时 Floyd算法的复杂度为O(V^3) 而Dijstra的复杂度是 O(E+VlogV) (用斐波那契堆)

10. 弗洛伊德算法如何去记录最短路径经过的每一个结点

用path数组的递归实现打印

例如：打印i,j之间的路径

当path[i][j]的值为k时，分别再去打印i,k和k,j之间的路径

如此递归直至两点间直接有边相连