算法详细讲解

《算法详细讲解》由会员分享，可在线阅读，更多相关《算法详细讲解（4页珍藏版）》请在装配图网上搜索。

1、问题描述实现Floyd算法，并求所示有向图中各顶点之间的最短路径及其长度。算法思想采用图的邻接矩阵存储，实现Floyd算法数组P存储是否存在中间点使长度缩短。 设计描述数据存储结构类型的定义：typedef struct MGraphchar vexs M AX_VE RTEX_N U M ;int arcsMAX_VERTEX_NUMMAX_VERTEX_NUM;int vex nunxarc num;GraphKind kind;MGraph;源程序# include#include/最大值/最人顶点个数#define INFINITY 1000#define MAX_VERTEX_NUM

2、 20 #defineTRUEl#define FALSE 0typedef enumDG, DN, UDG, UDNGraphKind;/四种图类型typedef struct MGraphcharvexsMAX_VERTEX_NUMj;顶点向量intarcsMAX_VERTEX_NUMMAX_VERTEX_NUM;/ 邻接矩阵intvexnumrcnum;/图的当前顶点数和弧数GraphKindki nd;图的种类标志MGraph;void find(int PMAX_VERTEX_NUMMAX_VERTEX_NUMMAX-VERTEX_NUM,MGraph G,int ajnt b);v

3、oid main() MGraph G; intDMAX_VERTEX_NUMMAX_VERTEX_NUM/PMAX_VERTEX_NUMMAX_VERTEX_NUMMAX_ VERTEX_NUM;int ywkabi；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”,&G.arcsvw);读入邻接矩阵/ Pvwk为TRUE,则从v到w的最短路径中含有k

4、节点/ Dvw从v到w的最短路径的长度for (v = 0; v G.vexnum; v+)for (w = 0; w G.vexnum; w+)Dvw = G.arcsvw;for (k = 0; k G.vexnum; k+)Pvwk = FALSE;if (Dvw INFINITY)Pvwv = Pvww =TRUE;for (k = 0; k G.vexnum; k+)for (v = 0; v G.vexnum; v+)for (w = 0; w G.vexnum; w+)if(Dvk + DkwDvw)Dvw = Dvk + Dkw;for (i = 0; i G.vexnum;

5、i+)Pvwi = Pvki|Pkwi;for(a=0; aG.vexnum; a+)for(b=0; bG.vexnum; b+)if(Dab INFINITY & a!=b)printf(M%c 到(:最短路径为,65+3,65+6);printf(,%ct/65+a);find(PzGza,b);printf(,%ct,/65+b);printf(“长度为 %d“,Dab);printfCV)；void find(int PMAX_VERTEX_NUMMAX_VERTEX_NUMMAX-VERTEX_NUM,MGraphGzint ajnt b)int k;for(k = 0; k G.

6、vexnum; k+) if(Pabk=TRUE & k!=a & k!=b) find(RG，a，k);printf(,%ct,/65+k); find(RGkb);测试结果5100010002睛揄入顶点数和弧数6 9 情鎰入邻接矩阵 0 3 1000 4 1000 5 1000 0 1 1000 10001000 10(0001000 3 10001000-3 0输入1000(1000为无穷！ 输出toMMV Mv 路路路路路路路路路路路路路路路路路路路路y 短短短短短短短短短短短短短短短短短短短短an 曰曹簪習昏曹昏S曹暫曹習麻S B CD F c D、F、B D F、B CJFB c

7、D F B c、D SreaaaabbbcccdddeeeefffpA A A A B B B C C C DD E EE E FF FB长度为3D节廈型4F*度为5 ck度为cF长度为5DD长度为5DB长度为3BBDD PvDDD长度为2continuec长度为4D长度为6B长度为84 8 6 为为为 度度度 长V长c F B BB长度为5BDBF长度为13BC长度为7BC长度为6心得体会二！ ！懂得了 floyd算法的思想，用邻接矩阵存储带权值的图。 问题主要出在输出打印方面Void findfint PMAX_VERTEX_NUMMAX_VERTEX_NUMMAX_VERTEX_NUM,MGraph G,int ajnt b)int k;for(k = 0; k G.vexnum; k+)if(Pabk=TRUE & k!=a & k!=b)find(BG,a,k);printf(,t%c/65+k);find(RGkb);采用递归的思想一次寻找是否存在中间点然后打印出来。问题出在红色部分，判定是否采用递归，未考虑k是否与a b相同，结呆导致无限递归。 从而发现stack overflow的错误提示有可能出于递归无法跳出，导致栈的溢出问题。