Floyd算法是什么?

有必要,因为
1、如果依次对某个顶点运用Dijkstra算法,则与Floyd算法相比,很多路径和结果计算是重复的,虽然复杂度相同,但是运算量差了很多；
2、更为重要的是：Dijkstra算法使用的前提是图中路径长度必须大于等于0；
但是Floyd算法则仅仅要求没有总和小于0的环路就可以了
因此Floyd 算法应用范围比Dijkstra算法要广.

Dijkstra 算法 在网络中用得多,一个一个节点添加,加一个点刷一次路由表.
Floyd 算法 ：把所有已经连接的路径都标出来,再通过不等式比较来更改路径.
实现过程不太相同.前一个是用在大网络中,对节点数目和具体连接不了解时候使用,后面是总体把握了,再对各连接具体路径进行修正.

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为止

先用floyd求出距离矩阵D,即以下代码中的矩阵B.
以下matlab程序为从12个点中选出3点,可以此类推.
clear all;
A=[combntns(1:12,3)]; %列出12个居民点选3个缴费点的所有情况.
for i=1:nchoosek(12,3) %for……end,循环,计算以上列出所有情况下所有居民需要行走的总路程!
A2=A(i,:);
A3=A2(1,1); %读取选取3个居民点
A4=A2(1,2);
A5=A2(1,3);
People=[15 10 12 18 5 24 11 16 13 22 19 20]; %每个居民点的人数的矩阵.
B=[
0 15 37 55 24 60 18 33 48 40 58 67;
15 0 22 40 38 52 33 48 42 55 61 61;
37 22 0 18 16 30 43 28 20 58 39 39;
55 40 18 0 34 12 61 46 24 62 43 34;
24 38 16 34 0 36 27 12 24 49 37 43;
60 52 30 12 36 0 57 42 12 50 31 22;
18 33 43 61 27 57 0 15 45 22 40 61;
33 48 28 46 12 42 15 0 30 37 25 46;
48 42 20 24 24 12 45 30 0 38 19 19;
40 55 58 62 49 50 22 37 38 0 19 40;
58 61 39 43 37 31 40 25 19 19 0 21;
67 61 39 34 43 22 61 46 19 40 21 0 ;
]; %居民到其他居民点所有最短的距离.
B1=B(:,A3); %居民点到所选的缴费点的理论最短距离.
B2=B(:,A4);
B3=B(:,A5);
C=[B1 B2 B3];
D=sort(C,2);
Shortjourney=D(:,1); %每位居民选择缴费点后需要行走的最短路程.
Sum(i)=People*Shortjourney; %所有居民所要行走的路程总和.
end
E=[reshape(Sum,nchoosek(12,3),1)]; %将以上得到的数组转为矩阵.
minposition=find(E==min(E)); %找出最小值在矩阵的位置.
A=[combntns(1:12,3)]; %A的顺序与E的一致!
position=A(minposition,:) %最佳的缴费点的选择.

C语言

　　#include

　　#define MAXV 100

　　#define INF 32767

　　#include "graph.h"

　　//extern void DispMat(MGraph g);

　　void DispMat(MGraph g)

　　{

　　int i,j;

　　for(i=0;i

一般来说都是一个东西,就是求图的没对点之间最短路的一种算法.一般都称作floyd.