算法详细讲解

问题描述实现Floyd算法，并求所示有向图中各顶点之间的最短路径及其长度。算法思想采用图的邻接矩阵存储，实现Floyd算法数组存储是否存在中间点使长度缩短。设计描述数据存储结构类型的定义：typedefstructMGraph(charvexs[MAX_VERTEX_NUM];intarcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];intvexnum^rcnum;GraphKindkind;)MGraph;源程序#include<stdlib.h>#include<stdio.h>//最大值//最大值//最大顶点个数#defineMAX_VERTEX_NUM20#defineTRUEl#defineFALSE0typedefenum(DG,DN,UDG,UDN}//四种图类型//四种图类型typedefstructMGraph(//顶点向量//顶点向量//邻接矩阵//图的当前顶点数和弧数//图的种类标志intarcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];intvexnum,arcnum;GraphKindkind;}MGraph;voidfind(intP[MAX_VERTEX_NUM][MAX_VERTEX_NUM][MAX_VERTEX_NUM],MGraphG,intajntb);voidmain()(MGraphG;intD[MAX_VERTEX_NUM][MAX_VERTEX_NUM]/P[MAX_VERTEX_NUM][MAX_VERTEX_NUM][MAX_VERTEX_NUM];intv,w,k,a,b,i;printfC'请输入顶点数和弧数“)；scanf("%d%d,l/&G.vexnum/&G.arcnum);G.kind=DG;printff'请输入邻接矩阵\n")；for(v=0;v<G.vexnum;v++)for(w=0;w<G.vexnum;w++)scanf("%d"z&G.arcs[v][w]); 〃读入邻接矩阵//P[v][w][k]为TRUE,则从v到w的最短路径中含有k节点//D[v][w]从v到w的最短路径的长度for(v=0;v<G.vexnum;v++)for(w=0;w<G.vexnum;w++)(D[v][w]=G.arcs[v][w];for(k=0;k<G.vexnum;k++)P[v][w][k]=FALSE;if(D[v][w]<INFINITY)P[v][w][v]=P[v][w][w]=TRUE;}for(k=0;k<G.vexnum;k++)for(v=0;v<G.vexnum;v++)for(w=0;w<G.vexnum;w++)if(D[v][k]+D[k][w]<D[v][w]){D[v][w]=D[v][k]+D[k][w];for(i=0;i<G.vexnum;i++)P[v][w][i]=P[v][k][i]||P[k][w][i];}for(a=0;a<G.vexnum;a++)for(b=0;b<G.vexnum;b++)if(D[a][b]<INFINITY&&a!=b){printf("％c到％(:最短路径为”,65+a,65+b);printf(,,%c\t"/65+a);find(PzGza,b);printf(”％c\t",65+b);printf(“长度为%d",D[a][b]);printfCV)；})voidfind(intP[MAX_VERTEX_NUM][MAX_VERTEX_NUM][MAX_VERTEX_NUM],MGraph

GJntajntb)(intk;for(k=0;k<G.vexnum;k++)if(P[a][b][k]==TRUE&&k!=a&&k!=b){find(P,G,a,k);printf("%c\t",65+k);find(P,G,k,b);}}测试结果博腌入顶点数和弧数69懵瑞入邻接矩阵0310004100055100051000100025I5I5.TOC\o"1-5"\h\z100010( 0005I5I5.100031 000输入1000一 30输入(1000为无穷！z输出to—MMV^Mv路路路路路路路路路路路路路路路路路路路路y短短短短短短短短短短短短短短短短短短短短an曰<瞽瞽<瞽瞽瞽>瞽瞽>瞽瞽S皆瞽>瞽瞽取to—MMV^Mv路路路路路路路路路路路路路路路路路路路路y短短短短短短短短短短短短短短短短短短短短an曰<瞽瞽<瞽瞽瞽>瞽瞽>瞽瞽S皆瞽>瞽瞽取SBCDFcdjfbDf、bc、f、bcdfbc、dsreAAnABBBCCCDDDEEEEFFFPAAAABBBCCCDDEEEEFFFB长度为3D长废*4F*度为5C长度为1QF长度为5DD长度为5D'B长度为3B

BD

D•PvDDD长度为2continuec长度为4D长度为6B长度为8DD486为为为度度度-fe-fe-feB长度为5B DB F长度为13B C长度为7B C长度为6心得体会~。！！憧得了floyd算法的思想，用邻接矩阵存储带权值的图。问题主要出在输出打印方面VoidfindfintP[MAX_VERTEX_NUM][MAX_VERTEX_NUM][MAX_VERTEX_NUM],MGraphG,intajntb)(intk;for(k=0;k<G.vexnum;k++)if(P[a][b][k]==TRUE&&k!=a&&k!=b){find(BG,a,k);printf(,,\t