资源描述：
《Dijkstra算法应用举例.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、Dijkstra算法应用举例20061002516张昕12306216某城市部分街道如下图所示求到其他点的最短距离。源程序如下#include#include#defineTRUE1#defineFALSE0#defineMAXV100#defineMAXDEGREE50#defineMAXINT100007intparent[MAXV];typedefstruct{intv;intweight;}edge;typedefstruct{edgeedges[MAXV+1][MAXDEGREE];intdegree[MAXV+1];intnvertices;i
2、ntnedges;}graph;initialize_graph(graph*g){inti;g->nvertices=0;g->nedges=0;for(i=1;i<=MAXV;i++)g->degree[i]=0;}insert_edge(graph*g,intx,inty,intdirected,intw){if(g->degree[x]>MAXDEGREE)printf("Warning:insertion(%d,%d)exceedsdegreebound",x,y);g->edges[x][g->degree[x]].v=y;g->edges[x][g->degree[x]].w
3、eight=w;g->degree[x]++;if(directed==FALSE)insert_edge(g,y,x,TRUE,w);elseg->nedges++;}read_graph(graph*g,intdirected){inti;intm;intx,y,w;initialize_graph(g);char*m_n="812";//eg314---v3节点与v1节点互连权值是4char*s[]={"122","135","143","234","256","344","365","474","563","584","675","684","786"};sscanf(m_n,"%d%
4、d",&(g->nvertices),&m);for(i=1;i<=m;i++){sscanf(s[i-1],"%d%d%d",&x,&y,&w);insert_edge(g,x,y,directed,w);}}find_path(intstart,intend,intparents[]){if((start==end)
5、
6、(end==-1))printf("%d",start);else{find_path(start,parents[end],parents);printf("%d",end);}}voiddijkstra(graph*g,intstart){inti,j;bool
7、intree[MAXV];intdistance[MAXV];intv;intw;intweight;intdist;for(i=1;i<=g->nvertices;i++){intree[i]=FALSE;distance[i]=MAXINT;parent[i]=-1;}distance[start]=0;v=start;while(intree[v]==FALSE){intree[v]=TRUE;for(i=0;idegree[v];i++){w=g->edges[v][i].v;weight=g->edges[v][i].weight;if(distance[w]>(distan
8、ce[v]+weight)){distance[w]=distance[v]+weight;parent[w]=v;}}v=1;dist=MAXINT;for(i=1;i<=g->nvertices;i++)if((intree[i]==FALSE)&&(dist>distance[i])){dist=distance[i];v=i;}}for(i=1;i<=g->nvertices;i++)printf("%d%d",i,distance[i]);}intmain(intargc,char**argv){graphg;inti,j;read_graph(&g,FALSE);for(j=1
9、;j<=8;j++){printf("");printf("输出到各点的最短路径长度");dijkstra(&g,j);printf("输出到各点的最短路径");for(i=1;i<=g.nvertices;i++)find_path(j,i,parent);printf("");}system("PAUSE");return0;}运行结果1到各点的最短路经及长度2到各点的最短路经
