最短路径c++实现代码.docVIP

#include iostream.h #include stdio.h #include conio.h #define infinty 1000 #define max_vertex_num 20 #define ok 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 typedef enum{dg,dn,udg,udn}graphkind; typedef int etype; typedef int infotype; typedef int vertextype; typedef int pathmatrix; typedef int shortpathtable; typedef struct arccell { etype adj; infotype info; }arccell,adjmatrix[max_vertex_num][max_vertex_num]; typedef struct { vertextype vexs[max_vertex_num]; adjmatrix arcs; int vexnum,arcnum; graphkind kind; }mgraph; int creatudn(mgraphg) { int i=0,j=0,k,vi,vj,w; cout请输入顶点个数:; cing.vexnum; cout输入边的条数:; cing.arcnum; for(i=0;ig.vexnum;++i) for(j=0;jg.vexnum;++j) { g.arcs[i][j].info=infinty; } cout请输入依附边的两个顶点:endl; for(k=0;kg.arcnum;++k) { coutendl请输入第k+1边的顶点vi(0v1=g.vexnum):; cinvi; cout请输入第k+1边的顶点vj(0v1=g.vexnum):; cinvj; cout请输入第k+1条边的权重(0weight:infinty):; cinw; i=vi; j=vj; while(i1||ig.vexnum||j1||jg.vexnum||w0||w=infinty) { coutendl请输入第k+1边的顶点vi(0v1=g.vexnum):endl; cinvi; cout请输入第k+1边的顶点vj(0v1=g.vexnum):; cinvj; cout请输入第k+1条边的权重(0weight:infinty):endl; cinw; i=vi; j=vj; } i--; j--; g.arcs[i][j].info=w; } return ok; } void shortestpath_dij(mgraph g,int v0,pathmatrix path[max_vertex_num][max_vertex_num],shortpathtable dist[max_vertex_num]) { int i,j,v,w,min,final[max_vertex_num]; for(v=0;vg.vexnum;++v)///输出第一个顶点的邻接路径 { final[v]=FALSE; dist[v]=g.arcs[v0][v].info; for(w=0;wg.vexnum;++w) path[v][w]=FALSE; if(dist[v]infinty) { //path[v][v0]=TRUE; //path[v][v]=TRUE; } } dist[v0]=0; final[v0]=TRUE; printf(vertice); for(i=0;ig.vexnum;i++) printf(%8d,i+1); printf(\n); printf(step%d:,v0+1); for(i=0;ig.vexnum;i++) printf(%8d,dist[i]); printf(\n); //////////////第一个邻接路径输出完毕! for(i=1;ig.vexnum;++i) { min=infinty; for(w=0;wg.vexnum;++w) if(!final[w]) if(dist[w]min) { v=w; min=dist[w]; } fi