Floyd算法与Dijkstra算法的不同

我来告诉你标准答案!Floyd算法又称为弗洛伊德算法，插点法，是一种用于寻找给定的加权图中顶点间最短路径的算法。
算法过程：1，从任意一条单边路径开始。所有两点之间的距离是边的权，或者无穷大，如果两点之间没有边相连。
2，对于每一对顶点u和v，看看是否存在一个顶点w使得从u到w再到v比己知的路径更短。如果是更新它。
Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。
　
算法步骤如下：
1初使时令S={V0},T={其余顶点}，T中顶点对应的距离值
若存在，d(V0,Vi)为弧上的权值
若不存在，d(V0,Vi)为∝
2从T中选取一个其距离值为最小的顶点W且不在S中，加入S
3对T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的
距离值比不加W的路径要短，则修改此距离值
重复上述步骤2、3，直到S中包含所有顶点，即S=T为止

你得到的R矩阵就是路径的矩阵，那么怎么看路径呢，假如你需要找出从点3到点8的路径，那么首先你查看R矩阵中R（3,8）是什么，比如是7，那么接下来就查看R（3，7），依次类推，直到R（3，i）=3,那么这条路径就是37,8

floyd算法本质是动态规划，可以写成三维来理解
f[k][i][j]表示如果除去起点和终点路径上只包含编号为1到k的点的话，从i号点走到j号点的最短路是f[k][i][j]
那么我们依次的扩大k，当k从1扩大到n，最终的答案也就得出
考虑如何从从k推到k+1。首先，最短路不可能经过k+1号点两次，所以一条包含k+1号点的最短路必然是由一段只包含1~k的点的路径P1+(k+1号点)+另一端只包含1~k的点的路径P2得出的，枚举起点i和终点j，拼接得的长度为f[k][i][k+1]+f[k][k+1][j]
仔细观察后又会发现，将第一维拿掉丝毫不影响答案，将第一维删除后，就得到了用两维数组存储的floyd算法。

floyd是动态规划的简化,所以输出路径一样套用dp的典型记录方式即可
即,每次松弛时,记录是松弛了哪一个点然后输出时递归输出即可
弄一个矩阵R[][]初始化为0,然后比如你的距离矩阵是D[][]
松弛改为是:
if(D[i][j] > D[i][k]+D[k][j]){
D[i][j] = D[i][k]+D[k][j];
R[i][j] = k;
}
输出时可以写一个递归函数
function out(a,b){
if(R[a][b] == 0){
return;
}
out(a,R[a][b]);
//输出k
out(R[a][b],b);
}

这个是M文件中的函数啊,只有运行在主界面并且这样运行:
floyd(a)(把a输入括号这里才行)
单独运行当然没有定义a啊
%floydm
%采用floyd算法计算图a中每对顶点最短路
%d是矩离矩阵
%r是路由矩阵
function[d,r]=floyd(a)
n=size(a,1);
d=a;
fori=1:n
forj=1:n
r(i,j)=j;%原始默认路径都是各节点间直接到达的距离
end
end
r
fork=1:n
fori=1:n
forj=1:n
ifd(i,k)+d(k,j)d(i,j)=d(i,k)+d(k,j);%这里是不是输入错了看不懂中间为甚么有个空格;
但总体意思是说如果从i节点先到k节点再到j节点间距离比从i直接到j要近的话就替换掉原先那条路径
r(i,j)=r(i,k)
end
end
end
k
d
r
end

A矩阵是邻接矩阵，对角线上为o，其余位置数字表示的是两点之间距离，比如A(1,2)=2,表示从第一个点到第二个点的距离为2inf是无穷大的意思，这里表示没有直接沟通这两点的路。
n=length(D);设定n为D矩阵的长度。
接下来的两重循环，得到的R矩阵是nn的矩阵，它每个数据表示的是路径，比如：R(1,3)=1;表示路径为：1-1-3这里是初始化路径了。
后面的三重循环是floyd算法的关键所在，就是更新路线了。里面的那个判断指的是：
假设有3个点，1
2
3；如果我从1-2-3之间总距离小于1-3的距离，那么我R(1,3)=2；这就是选取更近的路线了。
最后的两个判断是为了不让曾经走过的点再次被遍历。就是不回头的意思了，这个一般都可以忽略了，你照打上去就是了。
不知道这样的解释你是否满意。

---