数据结构与算法:Floyd算法_第1页
数据结构与算法:Floyd算法_第2页
数据结构与算法:Floyd算法_第3页
数据结构与算法:Floyd算法_第4页
全文预览已结束

下载本文档

kok电子竞技权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

kok电子竞技:文档简介

问题描述实现Floyd算法,并求所示有向图中各顶点之间的最短路径及其长度。算法思想采用图的邻接矩阵存储,实现Floyd算法~,数组P[][][]存储是否存在中间点使长度缩短。设计描述数据存储结构类型的定义:typedefstructMGraph{charvexs[MAX_VERTEX_NUM];intarcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];intvexnum,arcnum;GraphKindkind;}MGraph;源程序#include<stdlib.h>#include<stdio.h>#defineINFINITY1000//最大值#defineMAX_VERTEX_NUM20//最大顶点个数#defineTRUE1#defineFALSE0typedefenum{DG,DN,UDG,UDN}GraphKind;//四种图类型typedefstructMGraph{charvexs[MAX_VERTEX_NUM];//顶点向量intarcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//邻接矩阵intvexnum,arcnum;//图的当前顶点数和弧数GraphKindkind;//图的种类标志}MGraph;voidfind(intP[MAX_VERTEX_NUM][MAX_VERTEX_NUM][MAX_VERTEX_NUM],MGraphG,inta,intb);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; printf("请输入顶点数和弧数"); scanf("%d%d",&G.vexnum,&G.arcnum); G.kind=DG; printf("请输入邻接矩阵\n");for(v=0;v<G.vexnum;v++)for(w=0;w<G.vexnum;w++) scanf("%d",&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到%c最短路径为",65+a,65+b); printf("%c\t",65+a); find(P,G,a,b); printf("%c\t",65+b); printf("长度为%d",D[a][b]); printf("\n"); }}voidfind(intP[MAX_VERTEX_NUM][MAX_VERTEX_NUM][MAX_VERTEX_NUM],MGraphG,inta,intb){ 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); }}测试结果输入(1000为无穷!~输出心得体会~。。 懂得了floyd算法的思想,用邻接矩阵存储带权值的图。 问题主要出在输出打印方面Voidfind(intP[MAX_VERTEX_NUM][MAX_VERTEX_NUM][MAX_VERTEX_NUM],MGraphG,inta,intb){ intk; for(k=0;k<G.vexnum;k++) if(P[a][b][k]==TRUE&&k!=a&&k!=b){ find(P,G,a,k); printf("\t%c",65+k); find(P,G,k,b); }}采用递归的思想一次寻找是否存在中间点然后打印出来。问题出在红色部分,判定是否采用递归,未考虑k是否与ab相同,结果导致无限递归。从而发现stackoverflow的错误提示有可能出于递归无法跳出,导致栈的溢出问题。

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论