扫二维码下载作业帮
2亿+学生的选择
下载作业帮安装包
扫二维码下载作业帮
2亿+学生的选择
用弗洛伊德算法求最短路径已知一有向网的邻接矩阵如下图所示,若需在其中一个结点建立娱乐中心,要求该结点距其他各结点的最长往返路程最短,相同条件下总的往返路程越短越好,问娱乐中心应选址何处?v1&&
∞& ∞& ∞&
2&& ∞& ∞
∞& ∞&& 0&
1&& ∞& ∞&
0&&& 3&&&v6&
∞& ∞&& 2&&
∞&& 0&&&&解题过程：v1&&
0&&&3&&&v6&
7&& 2&& 5&
6&& 0&&设Vj到各顶点的往返距离和为S（Vj）到其他各顶点的最长往返路程为L（Vj）,则L（V1）＝9,S（V1）＝37L（V2）＝13,S（V2）＝34L（V3）＝12,S（V3）＝46L（V4）＝12,S（V4）＝34L（V5）＝9,S（V5）＝34L（V6）＝13,S（V6）＝49我会画出图,但是L和S怎么求出来的?
扫二维码下载作业帮
2亿+学生的选择
是地信的题吧,先给你说v1怎么求,先找出v1能去的最近的点,为V2,如果S1i>S12+S2i修改V1到Vi的距离为S12+S2i然后去掉V2,在其余的点中找距V1最近的,按上面的方法修改最后得到V1与其他各点的最短距离同样的方法求出到其他点的最短距离
其他类似问题
扫描下载二维码4790人阅读
C and C++（401）
Data Structure（129）
Algorithm（431）
Floyd算法又称为插点法，是一种用于寻找给定的加权图中多源点之间最短路径的算法。
通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。
从图的带权邻接矩阵A=[a(i,j)] n×n开始，递归的进行n次更新，即由矩阵D(0)=A，按一个公式，构造出矩阵D(1)；
又用同样地公式由D(1)构造出D(2)；……；最后又用同样的公式由D(n-1)构造出矩阵D(n)。矩阵D(n)
的 i 行 j 列元素便是 i 号顶点到 j 号顶点的最短路径长度，称D(n)为图的距离矩阵，同时还可引入一个后继节点
矩阵path来记录两点间的最短路径。采用松弛技术（松弛操作），对在i和j之间的所有其他点进行一次松弛。所以时间复杂度为O(n^3);
状态转移方程：
&&& 此算法属于DP（动态规划）
其状态转移方程如下map[i , j] =min{ map[i , k] + map[k , j] , map[i , j] }；
map[i , j]表示 i 到 j 的最短距离，K是穷举 i& ,& j 的断点，map[n , n]初值应该为0，或者按照题目意思来做。
当然，如果这条路没有通的话，还必须特殊处理，比如没有map[i , k]这条路。
&&& 1，从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。
&&& 2，对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比已知的路径更短。如果是更新它。
把图用邻接矩阵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直接相连。
&&&&&& Floyd算法适用于APSP(All Pairs Shortest Paths，多源最短路径)，是一种动态规划算法，稠密图效果最佳，边权可正可负。
此算法简单有效，由于三重循环结构紧凑，对于稠密图，效率要高于执行|V|次迪杰斯特拉算法，也要高于执行V次SPFA(队列优化的单源最短路)。
优点：容易理解，可以算出任意两个节点之间的最短距离，代码编写简单。
缺点：时间复杂度比较高，不适合计算大量数据。
代码段如下：
//弗洛伊德算法Floyd代码段
#define MAXVEX 65535
typedef int Pathmatirx[MAXVEX][MAXVEX];
typedef int ShortPathTable[MAXVEX][MAXVEX];
*Floyd算法，求网图G中各顶点V到各其余顶点w最短路径P[v][w]，及带权长度D[V][W].
*该算法的主要功能是求一个图中任意两点之间的最短距离。
void ShortestPath_Floyd(MGraph G, Pathmatrix *P, ShortPathTable *D)
for(v = 0; v & G.numV ++v)
for(w = 0; w & G.numV ++w)
(*D)[v][w] = G.matrix[v][w];
(*p)[v][w] =
//如果经过下标为k顶点路径比原来两点间路径更短
//将当前两点间权值设置为更小的一个
for(k = 0; k & G.numV ++k)
for(v = 0; v & G.numV ++v)
for(w = 0; w & G.numV ++w)
if((*D)[v][w] & (*D)[v][k] + (*D)[k][w])
(*D)[v][w] = (*D)[v][k] + (*D)[k][w];
//路径直射经过下标为k的顶点
(*P)[v][w] = (*P)[v][k];
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：1102487次
积分：23670
积分：23670
排名：第282名
原创：1306篇
转载：21篇
评论：215条
文章：33篇
阅读：10113
文章：62篇
阅读：24596
阅读：1436
阅读：2770
阅读：4195
文章：296篇
阅读：215441
文章：92篇
阅读：70501
文章：21篇
阅读：8473
文章：68篇
阅读：33967
文章：21篇
阅读：18762
文章：59篇
阅读：98369
文章：243篇
阅读：203924
文章：120篇
阅读：167318
文章：110篇
阅读：97515
文章：13篇
阅读：12935
文章：123篇
阅读：92854
(5)(24)(24)(35)(18)(18)(22)(15)(20)(38)(34)(41)(29)(42)(44)(16)(25)(13)(22)(27)(14)(4)(2)(17)(15)(11)(21)(31)(83)(65)(34)(29)(80)(79)(75)(43)(9)(52)(37)(45)(42)(34)(1)【图文】弗洛伊德算法_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
弗洛伊德算法
大小：160.00KB
登录百度文库，专享文档复制特权，财富值每天免费拿！
你可能喜欢==========================
==========================
Distance:110
Path:2-->3-->5-->6-->7
==========================
==========================
Distance:40
Path:3-->4
==========================
==========================
Distance:25
Path:3-->5
==========================
==========================
Distance:35
Path:3-->5-->6
==========================
==========================
Distance:85
Path:3-->5-->6-->7
==========================
==========================
Distance:55
Path:4-->5
==========================
==========================
Distance:65
Path:4-->5-->6
==========================
==========================
Distance:115
Path:4-->5-->6-->7
==========================
==========================
Distance:10
Path:5-->6
==========================
==========================
Distance:60
Path:5-->6-->7
==========================
==========================
Distance:50
Path:6-->7
Matlab源代码
function Floyd(w,router_direction,MAX)
%x为此图的距离矩阵
%router_direction为路由类型：0为前向路由；非0为回溯路由
%MAX是数据输入时的∞的实际值
len=length(w);
flag=zeros(1,len);
%根据路由类型初始化路由表
R=zeros(len,len);
for i=1:len
if router_direction==0%前向路由
R(:,i)=ones(len,1)*i;
else %回溯路由
R(i,:)=ones(len,1)*i;
disp('w(0)');
dispit(w,0);
disp('R(0)');
dispit(R,1);
%处理端点有权的问题
for i=1:len
tmp=w(i,i)/2;
w(i,:)=w(i,:)+
w(:,i)=w(:,i)+
flag(i)=1;
%Floyd算法具体实现过程
for i=1:len
for j=1:len
if j==i||w(j,i)==MAX
for k=1:len
if k==i||w(j,i)==MAX
if w(j,i)+w(i,k)
w(j,k)=w(j,i)+w(i,k);
if router_direction==0%前向路由
R(j,k)=R(j,i);
else %回溯路由
R(j,k)=R(i,k);
%显示每次的计算结果
disp(['w(',num2str(i),')'])
dispit(w,0);
disp(['R(',num2str(i),')'])
dispit(R,1);
%中心和中点的确定
[Center,index]=min(max(w'));
disp(['中心是V',num2str(index)]);
[Middle,index]=min(sum(w'));
disp(['中点是V',num2str(index)]);
function dispit(x,flag)
%x：需要显示的矩阵
%flag：为0时表示显示w矩阵，非0时表示显示R矩阵
len=length(x);
for j=1:len
if flag==0
s=[s sprintf('%5.2f\t',x(j,:))];
s=[s sprintf('%d\t',x(j,:))];
s=[s sprintf('\n')];
disp('---------------------------------------------------');
% 选择后按Ctrl+t取消注释号%
% 0,100,100,1.2,9.2,100,0.5;
% 100,0,100,5,100,3.1,2;
% 100,100,0,100,100,4,1.5;
% 1.2,5,100,0,6.7,100,100;
% 9.2,100,100,6.7,0,15.6,100;
% 100,3.1,4,100,15.6,0,100;
% 0.5,2,1.5,100,100,100,0
% 0,9.2,1.1,3.5,100,100;
% 1.3,0,4.7,100,7.2,100;
% 2.5,100,0,100,1.8,100;
% 100,100,5.3,0,2.4,7.5;
% 100,6.4,2.2,8.9,0,5.1;
% 7.7,100,2.7,100,2.1,0
% Floyd(a,1,100)
% Floyd(b,1,100)
pascal语言
k,n,i,j,x:
a:array[1..10,1..10]
path:array[1..10,1..10]
readln(n);
for i:=1 to n do
for j:=1 to n do
if k0 then
path[i,j]:=j;
for x:=1 to n do
for i:=1 to n do
for j:=1 to n do
if a[i,j]>a[i,x]+a[x,j] then
a[i,j]:=a[i,x]+a[x,j];
path[i,j]:=path[i,x];
readln(st,en);
writeln(a[st,en]);
while fen do
write('-->');
f:=path[f,en];
writeln(en);
//以无向图G为入口，得出任意两点之间的路径长度length[i][j]，路径path[i][j][k]，
//途中无连接得点距离用0表示，点自身也用0表示
public class FLOYD {
int[][] length =// 任意两点之间路径长度
int[][][] path =// 任意两点之间的路径
public FLOYD(int[][] G) {
int MAX = 100;int row = G.// 图G的行数
int[][] spot = new int[row][row];// 定义任意两点之间经过的点
int[] onePath = new int[row];// 记录一条路径
length = new int[row][row];
path = new int[row][row][];
for (int i = 0; i< i++)// 处理图两点之间的路径
for (int j = 0; j< j++) {
if (G[i][j] == 0)G[i][j] = MAX;// 没有路径的2个点之间的路径为默认最大
if (i == j)G[i][j] = 0;// 本身的路径长度为0
for (int i = 0; i< i++)// 初始化为任意两点之间没有路径
for (int j = 0; j< j++)
spot[i][j] = -1;
for (int i = 0; i< i++)// 假设任意两点之间的没有路径
onePath[i] = -1;
for (int v = 0; v< ++v)
for (int w = 0; w< ++w)
length[v][w] = G[v][w];
for (int u = 0; u< ++u)
for (int v = 0; v< ++v)
for (int w = 0; w< ++w)
if (length[v][w] >length[v][u] + length[u][w]) {
length[v][w] = length[v][u] + length[u][w];// 如果存在更短路径则取更短路径
spot[v][w] =// 把经过的点加入
for (int i = 0; i< i++) {// 求出所有的路径
int[] point =
for (int j = 0; j< j++) {
point = 0;
onePath[point++] =
outputPath(spot, i, j, onePath, point);
path[i][j] = new int[point];
for (int s = 0; s< s++)
path[i][j][s] = onePath[s];
void outputPath(int[][] spot, int i, int j, int[] onePath, int[] point) {// 输出i// 到j// 的路径的实际代码，point[]记录一条路径的长度
if (i == j)
if (spot[i][j] == -1)
onePath[point++] =
// System.out.print(" "+j+" ");
outputPath(spot, i, spot[i][j], onePath, point);
outputPath(spot, spot[i][j], j, onePath, point);
public static void main(String[] args) {
int data[][] = {
{ 0, 27, 44, 17, 11, 27, 42, 0, 0, 0, 20, 25, 21, 21, 18, 27, 0 },// x1
{ 27, 0, 31, 27, 49, 0, 0, 0, 0, 0, 0, 0, 52, 21, 41, 0, 0 },// 1
{ 44, 31, 0, 19, 0, 27, 32, 0, 0, 0, 47, 0, 0, 0, 32, 0, 0 },// 2
{ 17, 27, 19, 0, 14, 0, 0, 0, 0, 0, 30, 0, 0, 0, 31, 0, 0 },// 3
{ 11, 49, 0, 14, 0, 13, 20, 0, 0, 28, 15, 0, 0, 0, 15, 25, 30 },// 4
{ 27, 0, 27, 0, 13, 0, 9, 21, 0, 26, 26, 0, 0, 0, 28, 29, 0 },// 5
{ 42, 0, 32, 0, 20, 9, 0, 13, 0, 32, 0, 0, 0, 0, 0, 33, 0 },// 6
{ 0, 0, 0, 0, 0, 21, 13, 0, 19, 0, 0, 0, 0, 0, 0, 0, 0 },// 7
{ 0, 0, 0, 0, 0, 0, 0, 19, 0, 11, 20, 0, 0, 0, 0, 33, 21 },// 8
{ 0, 0, 0, 0, 28, 26, 32, 0, 11, 0, 10, 20, 0, 0, 29, 14, 13 },// 9
{ 20, 0, 47, 30, 15, 26, 0, 0, 20, 10, 0, 18, 0, 0, 14, 9, 20 },// 10
{ 25, 0, 0, 0, 0, 0, 0, 0, 0, 20, 18, 0, 23, 0, 0, 14, 0 },// 11
{ 21, 52, 0, 0, 0, 0, 0, 0, 0, 0, 0, 23, 0, 27, 22, 0, 0 },// 12
{ 21, 21, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 27, 0, 0, 0, 0 },// 13
{ 18, 41, 32, 31, 15, 28, 0, 0, 0, 29, 14, 0, 22, 0, 0, 11, 0 },// 14
{ 27, 0, 0, 0, 25, 29, 33, 0, 33, 14, 9, 14, 0, 0, 11, 0, 9 },// 15
{ 0, 0, 0, 0, 30, 0, 0, 0, 21, 13, 20, 0, 0, 0, 0, 9, 0 } // 16
for (int i = 0; i< data. i++)
for (int j = j< data. j++)
if (data[i][j] != data[j][i])
FLOYD test=new FLOYD(data);
for (int i = 0; i< data. i++)
for (int j = j< data[i]. j++) {
System.out.println();
System.out.print("From " + i + " to " + j + " path is: ");
for (int k = 0; k< test.path[i][j]. k++)
System.out.print(test.path[i][j][k] + " ");
System.out.println();
System.out.println("From " + i + " to " + j + " length :"+ test.length[i][j]);
篇二 : floyd最短路算法
Floyd最短路径算法（转）在图论中经常会遇到这样的问题，在1个有向图里，求出任意2个节点之间的最短距离。我们在离散数学、数据结构课上都遇到过这个问题，在计算机网络里介绍网络层之际好像也遇到过这个问题，记不请了...但是书本上一律采取的是Dijkstra算法，通过Dijkstra算法可以求出单源最短路径，然后逐个节点利用Dijkstra算法即可了。不过在这里想换换口味，采取RobertFloyd提出的算法来解决这个问题。下面让我们先把问题稍微的形式化一下：
如果有1个矩阵D=[d(ij)]，其中d(ij)&0表示i城市到j城市的距离。若i与j之间无路可通，那么d(ij)就是无穷大。又有d(ii)=0。编写1个程序，通过这个距离矩阵D，把任意2个城市之间的最短与其行径的路径找出来。
我们可以将问题分解，先找出最短的距离，然后在考虑如何找出对应的行进路线。如何找出最短路径呢，这里还是用到动态规划的知识，对于任何1个城市而言，i到j的最短距离不外乎存在经过i与j之间的k和不经过k2种可能，所以可以令k=1，2，3，...，n(n是城市的数目)，在检查d(ij)与d(ik)+d(kj)的值；在此d(ik)与d(kj)分别是目前为止所知道的i到k与k到j的最短距离，因此d(ik)+d(kj)就是i到j经过k的最短距离。所以，若有d(ij)&d(ik)+d(kj)，就表示从i出发经过k再到j的距离要比原来的i到j距离短，自然把i到j的d(ij)重写为d(ik)+d(kj)，每当1个k查完了，d(ij)就是目前的i到j的最短距离。重复这一过程，最后当查完所有的k时，d(ij)里面存放的就是i到j之间的最短距离了。所以我们即可用3个for循环把问题搞定了，但是有1个问题需要注意，那就是for循环的嵌套的顺序：我们可能随手就会写出这样的程序，但是仔细考虑的话，会发现是有问题的。for(int i=0; i&n;i++)
for(int j=0; j&n; j++)
for(int k=0; k&n; k++)
问题出在我们太早的把i-k-j的距离确定下来了，假设一旦找到了i-p-j最短的距离后，i到j就相当处理完了，以后不会在改变了，一旦以后有使i到j的更短的距离时也不能再去更新了，所以结果一定是不对的。所以应当象下面一样来写程序：
for(int k=0; k&n;k++)
for(int i=0; i&n; i++)
for(int j=0; j&n; j++)
这样作的意义在于固定了k，把所有i到j而经过k的距离找出来，然后象开头所提到的那样进行比较和重写，因为k是在最外层的，所以会把所有的i到j都处理完后，才会移动到下1个k，这样就不会有问题了，看来多层循环之际，我们一定要当心，否则很容易就弄错了。
接下来就要看一看如何找出最短路径所行经的城市了，这里要用到另1个矩阵P，它的定义是这样的：p(ij)的值如果为p，就表示i到j的最短行经为i-&...-&p-&j，也就是说p是i到j的最短行径中的j之前的最后1个城市。P矩阵的初值为p(ij)=i。有了这个矩阵之后，要找最短路径就轻而易举了。对于i到j而言找出p(ij)，令为p，就知道了路径i-&...-&p-&j；再去找p(ip)，如果值为q，i到p的最短路径为i-&...-&q-&p；再去找p(iq)，如果值为r，i到q的最短路径为i-&...-&r-&q；所以一再反复，到了某个p(it)的值为i时，就表示i到t的最短路径为i-&t，就会的到答案了，i到j的最短行径为i-&t-&...-&q-&p-&j。因为上述的算法是从终点到起点的顺序找出来的，所以输出之际要把它倒过来。
但是，如何动态的回填P矩阵的值呢？回想一下，当d(ij)&d(ik)+d(kj)时，就要让i到j的最短路径改为走i-&...-&k-&...-&j这一条路，但是d(kj)的值是已知的，换句话说，就是k-&...-&j这条路是已知的，所以k-&...-&j这条路上j的上1个城市(即p(kj))也是已知的，当然，因为要改走i-&...-&k-&...-&j这一条路，j的上1个城市正好是p(kj)。所以一旦发现d(ij)&d(ik)+d(kj)，就把p(kj)存入p(ij)。
下面是具体的C代码：
#define MAXSIZE 20
void floyd(int [][MAXSIZE], int[][MAXSIZE], int);
void display_path(int [][MAXSIZE], int [][MAXSIZE], int);
void reverse(int [], int);
void readin(int [][MAXSIZE], int *);
#define MAXSUM(a, b) (((a) !=INT_MAX && (b) != INT_MAX) ?\
((a) + (b)) : INT_MAX)
void floyd(int dist[][MAXSIZE], intpath[][MAXSIZE], int n)
for (i = 0; i & i++)
for (j = 0; j & j++)
path[i][j] =
for (k = 0; k & k++)
for (i = 0; i & i++)
for (j = 0; j & j++)
if (dist[i][j] & MAXSUM(dist[i][k],dist[k][j]))
path[i][j] = path[k][j];
dist[i][j] = MAXSUM(dist[i][k], dist[k][j]);
void display_path(intdist[][MAXSIZE], int path[][MAXSIZE], int n)
printf("\n\nOrigin-&Dest Dist Path");
printf( "\n-----------------------------");
chain = (int *) malloc(sizeof(int)*n);
for (i = 0; i & i++)
for (j = 0; j & j++)
if (i != j)
printf("\nm-&%d ", i+1, j+1);
if (dist[i][j] == INT_MAX)
printf(" NA ");
printf("M ", dist[i][j]);
count = 0;
k = chain[count++] = path[i][k];
} while (i != k);
reverse(chain, count);
printf("%d", chain[0]+1);
for (k = 1; k & k++)
printf("-&%d", chain[k]+1);
printf("-&%d", j+1);
free(chain);
#define SWAP(a, b) { temp = a =b; b = }
void reverse(int x[], int n)
int i, j, te[）
for (i = 0, j = n-1; i & i++, j--)
SWAP(x[i], x[j]);
void readin(int dist[][MAXSIZE],int *number)
int origin, dest, length,
char line[100];
gets(line);
sscanf(line, "%d", &n);
for (i = 0; i & i++)
for (j = 0; j & j++)
dist[i][j] = INT_MAX;
dist[i][i] = 0;
gets(line);
sscanf(line, "%d%d%d", &origin,&dest, &length);
while (origin != 0 && dest != 0&& length != 0)
dist[origin-1][dest-1] =
gets(line);
sscanf(line, "%d%d%d", &origin,&dest, &length);
测试程序如下所示：
int main(void)
int dist[MAXSIZE][MAXSIZE];
int path[MAXSIZE][MAXSIZE];
printf("\nInput the path information:");
printf("\n----------------------------\n");
readin(dist, &n);
floyd(dist, path, n);
display_path(dist, path, n);
getchar();
其中readin函数规定了输入的格式，第一列是指出有多少个城市；第二列以后每行3个数；第1个和第二个是一条路径的起点和终点，第3个数是路径的长度，最后以3个0作为输入结束条件。下面是1个输入的例子：
Input the path information:
--------------------------------------
对应的输出结果为：
Origin-&DestDist Path
----------------------------------------------
1-&2 5 1-&2
1-&3 151-&2-&4-&3
1-&4 10 1-&2-&4
2-&1 20 2-&4-&1
2-&3 10 2-&4-&3
2-&4 5 2-&4
3-&1 30 3-&1
3-&2 35 3-&1-&2
3-&4 15 3-&4
4-&1 15 4-&1
4-&2 20 4-&1-&2
4-&3 5 4-&3上一篇：下一篇：猜你喜欢微尘陌上艺文黄宏宣颜文若蝴蝶鱼子隽芹菜丨丶独自推荐图文网友评论评论（...）评论全部评论20141413182016131315本类最新09-0509-0509-0509-0509-0509-0509-0509-0509-0509-05最新范文01-0101-0101-0101-0101-0101-0101-0101-0101-0101-0101-0101-0101-0101-0101-01Floyd算法求解最短路径问题(完整程序代码)_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
Floyd算法求解最短路径问题(完整程序代码)
&&Floyd算法求解最短路径问题(完整程序代码)
阅读已结束，下载文档到电脑
想免费下载本文？
定制HR最喜欢的简历
下载文档到电脑，方便使用
还剩13页未读，继续阅读
定制HR最喜欢的简历
你可能喜欢