博客访问： 959932
博文数量： 267
博客积分： 1305
博客等级： 军士长
技术积分： 4523
注册时间：
不懂的东西还有很多，随着不断的学习，不懂的东西更多，无法消灭更多不懂的东西，那就不断的充实自己吧。
IT168企业级官微
微信号：IT168qiye
系统架构师大会
微信号：SACC2013
分类： C/C++
& & 上一篇文章我们通过迪杰斯特拉算法解决了从某个源点到其余各顶点的最短路径问题。从循环嵌套很容易得到此算法的时间复杂度为O(n^2)。可是怎么只找到从源点到某一个特定终点的最短路径，其实这个问题和求源点到其他所有顶点的最短路径一样复杂，时间复杂度依然是O(n^2)。
& & 此时比较简单方法就是对每个顶点当作源点运行一次迪杰斯特拉算法，等于在原有算法的基础上，再来一次循环，此时整个算法的时间复杂度为O(n^3)。
& & 对此，我们再来学习另一个求最短路径的算法——弗洛伊德（Floyd），它求所有顶点到所有顶点的最短路径，时间复杂度也为O(n^3)，但其算法非常简洁优雅。
& & 为了能讲明白该算法的精妙所在，先来看最简单的案例。下图左部分是一个最简单的3个顶点连通网图。
& & 先定义两个数组D[3][3]和P[3][3]，D代表顶点到顶点的最短路径权值和的矩阵，P代表对应顶点的最小路径的前驱矩阵。在未分析任何顶点之前，我们将D命名为D-1&&，其实它就是初始的图的邻接矩阵。将P命名为P-1&，初始化为图中所示的矩阵。
& & 首先，我们来分析，所有的顶点经过v0后到达另一顶点的最短距离。因为只有三个顶点，因此需要查看v1->v0->v2，得到D-1&[1][0] + D-1&[0][2] = 2 + 1 = 3。D-1&[1][2]表示的是v1->v2的权值是5，我们发现D-1&[1][2] >&D-1&[1][0] +&D-1&[0][2]，通俗的讲就是v1->v0->v2比直接v1->v2距离还要近。所以我们就让D-1&[1][2] &=&D-1&[1][0] +&D-1&[0][2]，同样的D-1&[2][1]& = 3，于是就有了D0&的矩阵。因为有了变化，所以P矩阵对应的P-1[1][2]和P-1[2][1]也修改为当前中转的顶点v0的下标0，于是就有了P0。也就是说：
&&&&--->动态规划乎
& & 接下来，其实也就是在D0和P0的基础上，继续处理所有顶点经过v1和v2后到达另一顶点的最短路径，得到D1和P1、D2和P2完成所有顶点到所有顶点的最短路径的计算。
& & 首先我们针对下图的左网图准备两个矩阵D-1和P-1，就是网图的邻接矩阵，初设为P[j][j] = j这样的矩阵，它主要用来存储路径。
& & 具体代码如下，注意是：求所有顶点到所有顶点的最短路径，因此Pathmatirx和ShortPathTable都是二维数组。
/* Floyd算法，求网图G中各顶点v到其余顶点w的最短路径P[v][w]及带权长度D[v][w]。 */
void ShortestPath_Floyd(MGraph G, Patharc *P, ShortPathTable *D)
&&&&int v,w,k;
&&&&for(v=0; v<G.numVertexes; ++v)&&&&&&&&&&&&/* 初始化D与P */
&&&&&&&&for(w=0; w<G.numVertexes; ++w)
&&&&&&&&&&&&(*D)[v][w]=G.arc[v][w];&&&&&&&&&&&&/* D[v][w]值即为对应点间的权值 */
&&&&&&&&&&&&(*P)[v][w]=w;&&&&&&&&&&&&&&&&&&&&/* 初始化P */
&&&&for(k=0; k<G.numVertexes; ++k)
&&&&&&&&for(v=0; v<G.numVertexes; ++v)
&&&&&&&&&&&&for(w=0; w<G.numVertexes; ++w)
&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&if ((*D)[v][w]>(*D)[v][k]+(*D)[k][w])
&&&&&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&&&&&/* 如果经过下标为k顶点路径比原两点间路径更短 */
&&&&&&&&&&&&&&&&&&&&
&&&&&&&&&&&&&&&&&&&&(*D)[v][w]=(*D)[v][k]+(*D)[k][w];&&&&/* 将当前两点间权值设为更小的一个 */
&&&&&&&&&&&&&&&&&&&&(*P)[v][w]=(*P)[v][k];&&&&&&&&&&&&&&&&/* 路径设置为经过下标为k的顶点 */
&&&&&&&&&&&&&&&&}
&&&&&&&&&&&&}
& & 下面介绍下详细的执行过程：
& & （1）程序开始运行，第4-11行就是初始化了D和P，使得它们成为 &&上图 & &的两个矩阵。从矩阵也得到，v0->v1路径权值为1，v0->v2路径权值为5，v0->v3无边连线，所以路径权值为极大值65535。
& & （2）第12~25行，是算法的主循环，一共三层嵌套，k代表的就是中转顶点的下标。v代表起始顶点，w代表结束顶点。
& & （3）当k = 0时，也就是所有的顶点都经过v0中转，计算是否有最短路径的变化。可惜结果是，没有任何变化，如下图所示。
& & （4）当k = 1时，也就是所有的顶点都经过v1中转。此时，当v = 0 时，原本D[0][2] = 5，现在由于D[0][1] + D[1][2] = 4。因此由代码的的第20行，二者取其最小值，得到D[0][2] = 4，同理可得D[0][3] = 8、D[0][4] = 6，当v = 2、3、4时，也修改了一些数据，请看下图左图中虚线框数据。由于这些最小权值的修正，所以在路径矩阵P上，也要做处理，将它们都改为当前的P[v][k]值，见代码第21行。
& & （5）接下来就是k = 2，一直到8结束，表示针对每个顶点做中转得到的计算结果，当然，我们也要清楚，D0是以D-1为基础，D1是以D0为基础，......，D8是以D7为基础的。最终，当k = 8时，两个矩阵数据如下图所示。
& & 至此，我们的最短路径就算是完成了。可以看到矩阵第v0行的数值与迪杰斯特拉算法求得的D数组的数值是完全相同。而且这里是所有顶点到所有顶点的最短路径权值和都可以计算出。
& & 那么如何由P这个路径数组得出具体的最短路径呢？以v0到v8为例，从上图的右图第v8列，P[0][8]= 1，得到要经过顶点v1，然后将1取代0，得到P[1][8] = 2，说明要经过v2，然后2取代1得到P[2][8] = 4，说明要经过v4，然后4取代2，得到P[4][8]= 3，说明要经过3，........，这样很容易就推倒出最终的最短路径值为v0->v1->v2->v4->v3->v6->v7->v8。
& & 求最短路径的显示代码可以这样写：
for(v=0; v<G.numVertexes; ++v)
&&&&&&&&for(w=v+1; w<G.numVertexes; w++)
&&&&&&&&&&&&printf("v%d-v%d weight: %d ",v,w,D[v][w]);
&&&&&&&&&&&&k=P[v][w];&&&&&&&&&&&&&&&&/* 获得第一个路径顶点下标 */
&&&&&&&&&&&&printf(" path: %d",v);&&&&/* 打印源点 */
&&&&&&&&&&&&while(k!=w)&&&&&&&&&&&&&&&&/* 如果路径顶点下标不是终点 */
&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&printf(" -> %d",k);&&&&/* 打印路径顶点 */
&&&&&&&&&&&&&&&&k=P[k][w];&&&&&&&&&&&&/* 获得下一个路径顶点下标 */
&&&&&&&&&&&&}
&&&&&&&&&&&&printf(" -> %d\n",w);&&&&/* 打印终点 */
&&&&&&&&printf("\n");
& & 总体的代码如下：
#include "stdio.h"
#include "stdlib.h"
#include "io.h"
#include "math.h"
#include "time.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXEDGE 20
#define MAXVEX 20
#define INFINITY 65535
typedef int Status;&&&&/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef struct
&&&&int vexs[MAXVEX];
&&&&int arc[MAXVEX][MAXVEX];
&&&&int numVertexes, numEdges;
typedef int Patharc[MAXVEX][MAXVEX];
typedef int ShortPathTable[MAXVEX][MAXVEX];
/* 构件图 */
void CreateMGraph(MGraph *G)
&&&&int i, j;
&&&&/* printf("请输入边数和顶点数:"); */
&&&&G->numEdges=16;
&&&&G->numVertexes=9;
&&&&for (i = 0; i < G->numVertexes; i++)/* 初始化图 */
&&&&&&&&G->vexs[i]=i;
&&&&for (i = 0; i < G->numVertexes; i++)/* 初始化图 */
&&&&&&&&for ( j = 0; j < G->numVertexes; j++)
&&&&&&&&&&&&if (i==j)
&&&&&&&&&&&&&&&&G->arc[i][j]=0;
&&&&&&&&&&&&else
&&&&&&&&&&&&&&&&G->arc[i][j] = G->arc[j][i] = INFINITY;
&&&&G->arc[0][1]=1;
&&&&G->arc[0][2]=5;
&&&&G->arc[1][2]=3;
&&&&G->arc[1][3]=7;
&&&&G->arc[1][4]=5;
&&&&G->arc[2][4]=1;
&&&&G->arc[2][5]=7;
&&&&G->arc[3][4]=2;
&&&&G->arc[3][6]=3;
&&&&G->arc[4][5]=3;
&&&&G->arc[4][6]=6;
&&&&G->arc[4][7]=9;
&&&&G->arc[5][7]=5;
&&&&G->arc[6][7]=2;
&&&&G->arc[6][8]=7;
&&&&G->arc[7][8]=4;
&&&&for(i = 0; i < G->numVertexes; i++)
&&&&&&&&for(j = i; j < G->numVertexes; j++)
&&&&&&&&&&&&G->arc[j][i] =G->arc[i][j];
/* Floyd算法，求网图G中各顶点v到其余顶点w的最短路径P[v][w]及带权长度D[v][w]。 */
void ShortestPath_Floyd(MGraph G, Patharc *P, ShortPathTable *D)
&&&&int v,w,k;
&&&&for(v=0; v<G.numVertexes; ++v) /* 初始化D与P */
&&&&&&&&for(w=0; w<G.numVertexes; ++w)
&&&&&&&&&&&&(*D)[v][w]=G.arc[v][w];&&&&/* D[v][w]值即为对应点间的权值 */
&&&&&&&&&&&&(*P)[v][w]=w;&&&&&&&&&&&&&&&&/* 初始化P */
&&&&for(k=0; k<G.numVertexes; ++k)
&&&&&&&&for(v=0; v<G.numVertexes; ++v)
&&&&&&&&&&&&for(w=0; w<G.numVertexes; ++w)
&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&if ((*D)[v][w]>(*D)[v][k]+(*D)[k][w])
&&&&&&&&&&&&&&&&{/* 如果经过下标为k顶点路径比原两点间路径更短 */
&&&&&&&&&&&&&&&&&&&&(*D)[v][w]=(*D)[v][k]+(*D)[k][w];/* 将当前两点间权值设为更小的一个 */
&&&&&&&&&&&&&&&&&&&&(*P)[v][w]=(*P)[v][k];/* 路径设置为经过下标为k的顶点 */
&&&&&&&&&&&&&&&&}
&&&&&&&&&&&&}
int main(void)
&&&&int v,w,k;
&&&&MGraph G;
&&&&Patharc P;
&&&&ShortPathTable D; /* 求某点到其余各点的最短路径 */
&&&&CreateMGraph(&G);
&&&&ShortestPath_Floyd(G,&P,&D);
&&&&printf("各顶点间最短路径如下:\n");
&&&&for(v=0; v<G.numVertexes; ++v)
&&&&&&&&for(w=v+1; w<G.numVertexes; w++)
&&&&&&&&&&&&printf("v%d-v%d weight: %d ",v,w,D[v][w]);
&&&&&&&&&&&&k=P[v][w];&&&&&&&&&&&&&&&&/* 获得第一个路径顶点下标 */
&&&&&&&&&&&&printf(" path: %d",v);&&&&/* 打印源点 */
&&&&&&&&&&&&while(k!=w)&&&&&&&&&&&&&&&&/* 如果路径顶点下标不是终点 */
&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&printf(" -> %d",k);&&&&/* 打印路径顶点 */
&&&&&&&&&&&&&&&&k=P[k][w];&&&&&&&&&&&&/* 获得下一个路径顶点下标 */
&&&&&&&&&&&&}
&&&&&&&&&&&&printf(" -> %d\n",w);&&&&/* 打印终点 */
&&&&&&&&printf("\n");
&&&&printf("最短路径D\n");
&&&&for(v=0; v<G.numVertexes; ++v)
&&&&&&&&for(w=0; w<G.numVertexes; ++w)
&&&&&&&&&&&&printf("%d\t",D[v][w]);
&&&&&&&&printf("\n");
&&&&printf("最短路径P\n");
&&&&for(v=0; v<G.numVertexes; ++v)
&&&&&&&&for(w=0; w<G.numVertexes; ++w)
&&&&&&&&&&&&printf("%d ",P[v][w]);
&&&&&&&&printf("\n");
&&&&return 0;
& & 引自：《大话数据结构》
阅读(14439) | 评论(1) | 转发(4) |
相关热门文章
给主人留下些什么吧！~~
nice，写的用心！
请登录后评论。文档分类：
下载后只包含 1 个 DOCX 格式的文档，没有任何的图纸或源代码，
下载前请先预览，预览内容跟原文是一样的，在线预览图片经过高度压缩，下载原文更清晰。
您的浏览器不支持进度条
淘豆网网友近日为您收集整理了关于java Floyd算法求解最短路径问题(完整程序代码)的文档，希望对您的工作和学习有所帮助。以下是文档介绍：交通运输学院课程设计1引言在图论中经常会遇到这样的问题,在一个有向图里求出任意两个节点之间的最短距离。当节点之间的权值是正值的时候,我们可以采用Dijkstra算法,用贪心策略加于解决。但当节点之间的权值有负数的时候,Dijkstra就行不通了,这里介绍另外一种算法—Floyd最短路径算法。对于任意图,选择存储结构存储图并实现FLOYD算法求解最短路经。将问题分解,分解为两方面。一是对于任意图的存储问题,第二个是实现FLOYD算法求解最短路经。首先对于图的创建选择合适的存储结构进行存储,对于合适的存储结构可以简化程序。本实验采用邻接矩阵存储。然后是实现FLOYD算法求解最短路经,在FLOYD算法中路径的长度即是图中两定点间边的权值,FLOYD算法要求输出任意两个顶点间的最短路径,而且经过的顶点也要输出。考虑到问题的特殊性,采用一个二维数组和一个三维数组进行存储。二维数组存储最短路径,三维数组存储路径经过的顶点,在进行适当的算法后对这两个数组进行输出即可。通过问题的分解,逐个解决,事先所要求的程序。最短路径算法问题是计算机科学、运筹学、地理信息系统和交通诱导、导航系统等领域研究的一个热点。传统的最短路径算法主要有Floyd算法和Dijkstra算法。Floyd算法用于计算所有结点之间的最短路径。Dijkstra算法则用于计算一个结点到其他所有结点的最短路径。Dijkstra算法是已经证明的能得出最短路径的最优解,但它的效率是一个很大的问题。对于具有n个结点的一个图,计算一个结点到图中其余结点最短路径的算法时间复杂度为O(n2)。对于一座大中型城市,地理结点数目可能达到几万个到几十万个,计算最短路径的时间开销将是非常巨大的。本文根据吴一民老师的建议,分析当前存在的各种求最短路径的算法,提出一种新的基于层次图的最短路径算法,即将一个平面图划分若干子图,子图抽象为一个高层图。最短路径的计算首先在高层图中进行,缩小了最短路径的查找范围,降低了最短路径计算的时间开销。由于可以动态计算子图间的阻抗函数,算法可适用于动态交通诱导系统。设计目的(1)培养学生分析解决问题的能力,掌握java语言的程序设计方法;(2)通过课程设计实践,训练并提高学生在统筹全局、结构设计、查阅设计资料和计算机编程方面的能力;(3)提高学生实践论文撰写能力。任务与要求: (1) 理论设计部分以课程设计论文的形式提交,格式必须按照课程设计论文标准格式进行书写和装订;(2) 课程设计报告(论文)包括要求的作业。交通运输学院课程设计2第一章 Floyd 算法1.1 最短路的定义最短路径问题是图论研究中的一个经典算法,旨在寻找图中两结点之间的最短路径。算法的具体形式包括:确定起点的最短路径问题即已知起始结点,求最短路径问题。在无向图中该问题与确定起点的问题完全等同,在有向图中该问题等同于把所有路经反转的确定起点的问题。确定起点终点的最短路径问题即已知起点和终点求两结点之间的最短路径。求距离最短路径问题求图中所有的最短路径。用于解决最短路径问题的算法被称为最短路径算法。单源最短路定义:给定一个赋权有向图 G =(V,E),记 G 中每一条弧 aij=(vi,vj)上的权为 W(aij)=Wij,有给定 G 中的一个起点 s 和重点 t,设 p 是 G 中从 s 到 t 的一条路,则定义路径 p 的权是 p 中有弧的权之和,记为 W(p),即:W(p)=( , )Vi Vj pWij又若 p*是图 G 中从 s 到 t 的一条路径,且满足W(p*)=min{W(p)|p 为 Vs 到 Vt 的路}试中对 G 的所有从 s 到 t 的路 p 取最小,则称 p*为从 s 到 t 的最短路,W(p*)为s 到 t 的最短距离。在一个图 G 中,求从 s 到 t 的最短路径和最短距离问题就称为最短路径问题。1.2 Floyd 的定义与思想1.2.1 Floyd 算法的定义Floyd 算法又称为弗洛伊德算法,插点法,是一种用于寻找给定的加权图中顶点间最短路径的算法。1.2.2 Floyd 算法的思想利用一个三重循环产生一个存储每个结点最短距离的矩阵.弗洛伊德算法仍然使用图的邻接矩阵 arcs[n+1][n+1]来存储带权有向图。算法的基本思想是:设置一个 n x n的矩阵 A(k),其中除对角线的元素都等于 0 外,其它元素 a(k)[i][j]表示顶点 i 到顶点 j 的路径长度,K 表示运算步骤。开始时,以任意两个顶点之间的有向边的权值作为路径长度,没有有向边时,路径长度为∞,当 K=0 时, A (0)[i][j]=arcs[i][j],以后逐步尝试在原路径中加入其它顶点作为中间顶点,如果增加中间顶点后,得到的路径比原来的路径长度减少了,则以此新路径代替原路径,修改矩阵元素。具体做法为:交通运输学院课程设计3第一步,让所有边上加入中间顶点 1,取 A[i][j]与 A[i][1]+A[1][j]中较小的值作A[i][j]的值,完成后得到 A(1),第二步,让所有边上加入中间顶点 2,取 A[i][j]与 A[i][2]+A[2][j]中较小的值,完成后得到 A(2)…,如此进行下去,当第 n 步完成后,得到 A(n),A(n)即为我们所求结果,A(n)[i][j]表示顶点 i 到顶点 j 的最短距离。因此,弗洛伊德算法可以描述为:A(0)[i][j]=arcs[i][j]; //arcs 为图的邻接矩阵A(k)[i][j]=min{A(k-1)[i][j],A(k-1)[i][k]+A(k-1)[k][j]}其中 k=1,2,…,n定义一个 n 阶方阵序列:D(-1), D(0), …, D(n-1).其中 D(-1)[i][j] = G.arcs[i][j];D(k)[i][j] = min { D(k-1)[i][j],D(k-1)[i][k] +D(k-1)[k][j] }, k = 0,1,…, n-1D(0)[i][j]是从顶点 vi 到 vj , 中间顶点是 v0 的最短路径的长度,D(k)[i][j]是从顶点 vi 到 vj , 中间顶点的序号不大于 k 的最短路径长度,D(n-1)[i][j]是从顶点 vi 到 vj 的最短路径长度。1.3 Floyd 算法描述通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。a) 初始化:D[u,v]=A[u,v]b) For k:=1 to nFor i:=1 to nFor j:=1 to nIf D[i,j]&D[i,k]+D[k,j] ThenD[I,j]:=D[I,k]+D[k,j];c) 算法结束:D 即为所有点对的最短路径矩阵从图的带权邻接矩阵 A=[a(i,j)] n×n 开始,递归地进行 n 次更新,即由矩阵 D(0)=A,按一个公式,构造出矩阵 D(1);又用同样地公式由 D(1)构造交通运输学院课程设计4出 D(2);……;最后又用同样的公式由 D(n-1)构造出矩阵 D(n)。矩阵 D(n)的 i 行 j 列元素便是 i 号顶点到 j 1播放器加载中，请稍候...
该用户其他文档
下载所得到的文件列表java Floyd算法求解最短路径问题(完整程序代码).docx
文档介绍：
交通运输学院课程设计1引言在图论中经常会遇到这样的问题,在一个有向图里求出任意两个节点之间的最短距离。当节点之间的权值是正值的时候,我们可以采用Dijkstra算法,用贪心策略加于解决。但当节点之间的权值有负数的时候,Dijkstra就行不通了,这里介绍另外一种算法—Floyd最短路径算法。对于任意图,选择存储结构存储图并实现FLOYD算法求解最短路经。将问题分解,分解为两方面。一是对于任意图的存储问题,第二个是实现FLOYD算法求解最短路经。首先对于图的创建选择合适的存储结构进行存储,对于合适的存储结构可以简化程序。本实验采用邻接矩阵存储。然后是实现FLOYD算法求解最短路经,在FLOYD算法中路径的长度即是图中两定点间边的权值,FLOYD算法要求输出任意两个顶点间的最短路径,而且经过的顶点也要输出。考虑到问题的特殊性,采用一个二维数组和一个三维数组进行存储。二维数组存储最短路径,三维数组存储路径经过的顶点,在进行适当的算法后对这两个数组进行输出即可。通过问题的分解,逐个解决,事先所要求的程序。最短路径算法问题是计算机科学、运筹学、地理信息系统和交通诱导、导航系统等领域研究的一个热点。传统的最短路径算法主要有Floyd算法和Dijkstra算法。Floyd算法用于...
内容来自淘豆网转载请标明出处.最短路径之Floyd算法
Dijkstra算法求某一个源点到其余各顶点时间复杂度是O(n^2)，但如果采用此算法，找从某一源点到某一特定终点的最短路径，复杂度仍为O(n^2)。
求每一对顶点之间的最短路径：
（1）每次以一个顶点为源点，重复执行Dijkstra算法n次。总的时间复杂度是O(n^3）；
（2）弗洛伊德（Floyd）算法：时间复杂度也是O(n^3)，但形式上更简单。
以如下的有线网为例：
邻接矩阵为：
利用floyd算法求得的每一对顶点之间的最短路径及其路径长度的过程如下图所示：
具体算法实现代码如下：
vcD4KPHByZSBjbGFzcz0="brush:">//Floyd算法，求网图G中各顶点v到其余顶点w的最短路径P[v][w]及带权长度D[v][w]
void ShortestPath_FLOYD(Graph *g, PathMatrix p[][MAX_VEX], ShortPathTable d[][MAX_VEX])
for (v = 0; v vexN v++)
for (w = 0; w vexN w++)
d[v][w] = g->arc[v][w];
//初始化权值d^-1和路径p^-1
for (k = 0; k vexN k++)
for (v = 0; v vexN v++)
for (w = 0; w vexN w++)
if (d[v][k] + d[k][w] < d[v][w]) //从v经k到w的一条更短的路径
d[v][w] = d[v][k] + d[k][w];
p[v][w] = p[v][k];
//路径设置为经过下标为k的顶点
}// ShortestPath_FLOYD 下面详细说明执行流程：
（1）程序开始运行，第05-10行代码用于初始化D和P，使得它们成为上图 红框框住的两个矩阵。
（2）第12-19行是算法的主循环，共三层嵌套，k代表的就是中转顶点的下标。v代表起始顶点，w代表结束顶点。
（3）当k = 0时，所有的顶点对间的最短距离都经过顶点A中转
因为只有三个顶点A、B和C：
查看B->A->C，得D-1[1][0] + D-1 [0][2] = 6 + 11 = 17 > D-1 [1][2] = 2，=> D0[1][2] = D-1 [1][2]，即D0[1][2]的值不变化。
查看C->A->B，得D-1 [2][0]+ D-1 [0][1] = 3 + 4 = 7 < D-1 [2][1] = ∞，=> D0[1][2] = D-1 [2][0] + D-1 [0][1]=7。因此就得到了数组D0，同时将数组p-1[2][1]的值修改为当前中转顶点的下标0，即p0[2][1] =
0，如此就得到了数组p0。
也就是说：
D0[i][j] = Min{D-1[i][j], D-1[i][k]+ D-1[k][j]}
一般地，Dk[i][j] = Min{Dk-1[i][j], Dk-1[i][k]+ Dk-1[k][j]}, 0<=k<=n-1，其中D-1[i][j] = G.arcs[i][j]。
（4）k = 1，所有的顶点对间的最短距离都经过顶点B中转：
查看A->B->C，得D0[0][1]+
D0 [1][2] = 4 + 2 = 6< D0 [0][2] = 11，=> D1[0][2]= D0[0][1] + D0 [1][2]=
6，同时将数组p1[0][2]的值修改为当前中转顶点的下标1，即p1[0][2]
查看C->B->A，得D0 [2][1]+
D0 [1][0] = ∞+ 6 =∞>
D0 [2][0] = 3，=> D1[2][0]= D0 [2][0] = 3，不改变。
（5）k = 2，所有的顶点对间的最短距离都经过顶点C中转：
查看A->C->B，D2 [0][1]不改变。
查看B->C->A，得D1 [1][2]+
D1 [2][0] = 2+ 3 =
5 < D1 [1][0] = 6，=> D2 [1][0] = D1 [1][2]+ D1 [2][0]，同时将数组p2 [1][0]的值修改为当前中转顶点的下标2，即p2 [1][0]
ps：D0是以D-1为基础，D1是以D0为基础，D2是以D1为基础的。最终，当k = 2时，两个矩阵数据为：
验证可以发现D2数组的第1行和Dijkstra计算出来的D数组结果数一样的。
那么如何由P这个路径数组得出具体的最短路径呢？跟Dijkstra算法得到矩阵p后获取某一路径序列是一致的：
以A到C为例，从上图下半部分的P矩阵的第2列，P[0][2]= 1，得到要经过顶点B，然后将1取代0，得到P[1][2] = 2(此时等于终点C的下标了，说明中间的顶点序列只有下标为1的顶点B)，推倒出最终的最短路径值为A->B->C。
代码如下：
// 查找从源点v到终点w的路径,并输出
void SearchPath(VertexType vex[], PathMatrix p[][MAX_VEX], int v, int w)
int que[MAX_VEX];
int tot = 0;
que[tot++] =
int tmp = p[v][w];
//到顶点下标w的路径上的上一个顶点下标
while(tmp != w)
que[tot++] =
tmp = p[tmp][w];
//到顶点下标tmp的路径上的上一个顶点下标
que[tot] =
for(int i = i >= 0; --i)
if(i != 0)
printf("%c -> ", vex[que[i]]);
printf("%c", vex[que[i]]);
}以上述有向网图为例，程序运行截图为：
html(打开不了呢，发布时总是提示无效url，删掉链接地址开头的http://后倒是不会再提示，但就打不开链接了，不知道怎么解决~)
(window.slotbydup=window.slotbydup || []).push({
id: '2467140',
container: s,
size: '1000,90',
display: 'inlay-fix'
(window.slotbydup=window.slotbydup || []).push({
id: '2467141',
container: s,
size: '1000,90',
display: 'inlay-fix'
(window.slotbydup=window.slotbydup || []).push({
id: '2467143',
container: s,
size: '1000,90',
display: 'inlay-fix'
(window.slotbydup=window.slotbydup || []).push({
id: '2467148',
container: s,
size: '1000,90',
display: 'inlay-fix'5068人阅读
数据结构（33）
Floyd算法和Dijkstar算法是用来获得图中两点最短路径的算法。Dijkstar算法最终能够得到一个节点到其他所有节点的最短路径，而Floyd算法最终能够找出每对点之间的最短距离。
Dijkstar算法
Dijkstra(迪杰斯特拉)算法是典型的单源算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN,
CLOSE表的方式，这里均采用永久和临时标号的方式。注意该算法要求图中不存在负权回路。
算法描述 (这里描述的是从节点1开始到各点的dijkstra算法，其中Wa-&b表示a-&b的边的权值，d(i)即为最短路径值)
1． 置集合S={2,3,...n}, 数组d(1)=0, d(i)=W1-&i(1,i之间存在边) or +无穷大(1.i之间不存在边)
2． 在S中，令d(j)=min{d(i),i属于S}，令S=S-{j}，若S为空集则算法结束，否则转3
3． 对全部i属于S,如果存在边j-&i，那么置d(i)=min{d(i), d(j)+Wj-&i}，转2
复杂度分析
Dijkstra 算法的时间复杂度为O(n^2)
空间复杂度取决于存储方式，邻接矩阵为O(n^2)
问题描述：给定图G，求其顶点t到其他所有点的最短路径。
算法描述：将图所有点的集合S分为两部分，V和S-V。V集合是已经得到最短路径的点的集合，在初始情况下V中只有一个顶点t，S-V是还未得到最短路径点的集合。然后，在每一次迭代过程中取得S-V集中到V集合任一点距离最短的点，将其加到V集合，从V-S集合删除。重复此过程直到S-V集合为空。
时间复杂度：
输入输出格式
&&&&&& 输入格式:
第1行:一个数n，代表有n个节点
第2-n+1行:每行n个数，代表图的邻接矩阵，没有边相连为-1
输出格式:
第1行:n-1个数，分别是1号节点到2-n号节点的最短路径
Java代码：
&package com.collonn.
import java.util.PriorityQ
* 带权有向图的单源最短路径&br/&
* Dijkstra算法-(迪杰斯特拉)算法&br/&
public class GrfDijkstra {
// 为了矩阵的输出更直观好看一些，本例中约定，路径权值取值范围为：[1,10]，权值为999表示无连通
// 并假设所有权值的和小于999
private final int MAX = 999;
// 顶点总数
// 顶点信息
private String[]
// 顶点矩阵
private int[][]
// 源点到各顶点的距离
private int[]
// 顶点是否已标记
private int[]
public GrfDijkstra(int total, String[] nodes) {
this.total =
this.nodes =
this.matirx = new int[total][total];
this.dis = new int[total];
this.mark = new int[total];
private void printMatrix() {
System.out.println(&--------- weighted directed matrix ---------&);
System.out.println(&---0---1---2---3---4---5---6---7---8---&);
System.out.println(&---A---B---C---D---E---F---G---H---I---&);
for (int i = 0; i & this. i++) {
System.out.print(&-& + this.nodes[i] + &|&);
for (int j = 0; j & this. j++) {
System.out.print(String.format(&%03d&, this.matirx[i][j]) + &-&);
System.out.print(&\n&);
System.out.println(&--------- weighted directed matrix ---------&);
* Dijkstra算法-(迪杰斯特拉)算法之迭代实现
* @param s
源点(起点)
public void dijkstra(int s) {
for (int i = 0; i & this. i++) {
// 初始化都未标记
this.mark[i] = 0;
// 给源点的直接邻接点加上初始权值
this.dis[i] = this.matirx[s][i];
// 将源点s加入已标记
this.mark[s] = 1;
// 顶点到自身的距离为0
this.dis[s] = 0;
// 临时最短距离
int min = -1;
// 临时最短距离的顶点
int k = -1;
this.printDis(0, &屌&, &初始化&);
// 除去源点s到自身的距离为0外，还要不断的进行距离修正(源点s到其它顶点(共total-1个)的最短距离)
for (int i = 1; i & this. i++) {
// 从当前最新的，源点到其它各顶点的距离信息数组dis[]中，找到一个没有标记过的，
// 并且距离(从源点到该某顶点)最短的顶点
min = MAX;
for (int j = 0; j & this. j++) {
if (this.mark[j] == 0 && this.dis[j] & min) {
min = this.dis[j];
// 标记该顶点
this.mark[k] = 1;
* 距离校正&br/&
for (int j = 0; j & this. j++) {
if (this.mark[j] == 0 && (this.matirx[k][j] + this.dis[k]) & this.dis[j]) {
this.dis[j] = this.matirx[k][j] + this.dis[k];
this.printDis(i, this.nodes[k], &进行中&);
* Dijkstra算法-(迪杰斯特拉)算法之优先队列实现
public void dijkstraPQ() {
// Item是PriorityQueue中元素，实现了Comparable接口，优先队列用此接口进行排序
class Item implements Comparable&Item& {
// 节点在数组的下标
// 到改节点的临时最小权值和
public Item(int idx, int weight) {
this.idx =
this.weight =
public int compareTo(Item item) {
if (this.weight == item.weight) {
} else if (this.weight & item.weight) {
return -1;
// 值较小的元素总是在优先队列的头部，值较大的元素总是在优先队列的尾部
PriorityQueue&Item& pq = new PriorityQueue&Item&();
// 将源点(即起点)加入到优先队列
pq.offer(new Item(0, 0));
Item itm =
while (!pq.isEmpty()) {
itm = pq.poll();
// 图中某节点下标
int idx = itm.
// 到某节点的临时最小权值和
int weight = itm.
// 如果该元素还未标记，则更新最小权值各
if (this.mark[idx] == 0) {
this.dis[idx] =
// 找出该元素(假设A)的所有未标记的邻接点(假设B)
// 则，源点到B的距离可表示为：(源点到A的距离) + (A到B的距离)
// 将源点到B的距离加入到优先队列中
for (int i = 0; i & this. i++) {
if (this.mark[i] == 0) {
pq.offer(new Item(i, this.dis[idx] + this.matirx[idx][i]));
private void printDis(int i, String node, String pre) {
System.out.print(&\n& + pre + &,& + node + &,& + i + &---&&);
for (int t = 0; t & this.dis. t++) {
System.out.print(t + &,&);
System.out.print(&\n& + pre + i + &---&&);
for (int t : this.dis) {
System.out.print(t + &,&);
System.out.print(&\n&);
// 初始化图数据
// 0---1---2---3---4---5---6---7---8---
// A---B---C---D---E---F---G---H---I---
private void initGrf() {
// 初始化矩阵为最大值(各节点都不连通)
for (int i = 0; i & this. i++) {
for (int j = 0; j & this. j++) {
if (i == j) {
this.matirx[i][j] = 0;
this.matirx[i][j] = MAX;
// 手动设置有向路径
// A-&B, A-&E, A-&D
this.matirx[0][1] = 2;
this.matirx[0][4] = 3;
this.matirx[0][3] = 1;
this.matirx[1][2] = 2;
this.matirx[2][5] = 1;
// D-&E, D-&G
this.matirx[3][4] = 5;
this.matirx[3][6] = 2;
// E-&F, E-&H
this.matirx[4][5] = 6;
this.matirx[4][7] = 1;
this.matirx[5][8] = 3;
this.matirx[6][7] = 4;
// H-&F, H-&I
this.matirx[7][5] = 1;
this.matirx[7][8] = 2;
public static void main(String[] args) {
String[] nodes = new String[] { &A&, &B&, &C&, &D&, &E&, &F&, &G&, &H&, &I& };
GrfDijkstra grf = new GrfDijkstra(nodes.length, nodes);
grf.initGrf();
grf.printMatrix();
System.out.println();
System.out.println(&------ Dijkstra算法-(迪杰斯特拉)算法之迭代开始 ------&);
grf.dijkstra(0);
grf.printDis(0, &屌&, &最终值&);
System.out.print(&\n&);
System.out.println(&------ Dijkstra算法-(迪杰斯特拉)算法之迭代结束 ------&);
System.out.println();
System.out.println(&------ Dijkstra算法-(迪杰斯特拉)算法之优先队列开始 ------&);
grf.dijkstraPQ();
grf.printDis(0, &屌&, &最终值&);
System.out.print(&\n&);
System.out.println(&------ Dijkstra算法-(迪杰斯特拉)算法之优先队列结束 ------&);
&Floyd算法
问题描述：给定图G，得到每个点对的最短距离。
算法描述：Floyd算法是一个动态规划算法，最初矩阵A0是图的邻接矩阵，AK矩阵表示从i到j的最短路径，这些路径不能能通过大于K的节点，最终的矩阵AN就是想要得到的矩阵了。那么AK矩阵与A(K+1)矩阵有什么关系呢？关系就是A(K+1)[i,j]=min(A(K)[i,j],A(K)[i,k]+A(K)[k,j]),也就是看加上K点后，是不是能找到更短的距离。
时间复杂度：O(|V|^3) 顶点数的三次方。
示例：一上面的图为例子，下面展示了矩阵系列的建立过程：
Java代码：
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：242436次
积分：3445
积分：3445
排名：第6539名
原创：92篇
转载：146篇
评论：40条
(1)(1)(1)(2)(1)(2)(9)(16)(19)(37)(19)(11)(1)(22)(5)(8)(1)(4)(6)(10)(1)(10)(3)(1)(4)(1)(8)(1)(2)(21)(12)
