下面是源程序,已经可以运行,但是还有个小问题,这个程序只能求出指定源点到指定终点的最短路径,老师要求的是:源点可任意指定;输出从源点到其余各顶点的最短路径希望各位大牛能帮我改下,应该是在dijkstra算法里面改,自己水平有限,希望各位尽快指点指点,明天就检查了。谢谢
#include"stdafx.h"
#include
#include
#include
#include
#include
#include
#include
#defineINF100000//最大值∞
#defineMAX_VERTEX_NUM20//最大顶点个数
usingnamespacestd;
//图的邻接矩阵存储表示
typedefstructArcCell
{
intadj;
}ArcCell,AdjMatrix[MAX_VERTEX_NUM+1][MAX_VERTEX_NUM+1];
typedefstruct
{
intvexs[MAX_VERTEX_NUM+1];
AdjMatrixarcs;
intvexnum,arcnum;
}MGraph;
intpath[MAX_VERTEX_NUM+1][MAX_VERTEX_NUM+1];
voidShortest_DIJ()//Dijkstra算法
{
system("cls");
printf("\nDijkstra算法\n");
printf("\n提示:没有权值的输入0表示,顶点编号从1开始!\n");
MGraphG;
intx,y,weight,bz=0,min;
intP[MAX_VERTEX_NUM+1][MAX_VERTEX_NUM+1],D[MAX_VERTEX_NUM+1],final[MAX_VERTEX_NUM+1],path_DIJ[MAX_VERTEX_NUM];
printf("\n输入顶点数:");
scanf("%d",&G.vexnum);
printf("\n输入邻接矩阵:\n");
for(inti=1;i",x,y,x);
while(!s.empty())
{
printf("%d->",s.top());
s.pop();
}
printf("\b\b\b\b(最短路径长度为:%d)",D[y]);
}
system("pause");
}
voidoutput(inti,intj)//输出最短路径函数
{
if(i==j)return;
if(path[j]==0)printf("%d->",j);
else
{
output(i,path[j]);
output(path[j],j);
}
}
voidShowProblem(){
printf("问题描述:\n");
printf("(1)以邻接表作存储结构\n");
printf("(2)源点可任意指定;输出从源点到其余各顶点的最短路径\n");
printf("(3)测试用例见题集p48图7.11\n");
system("pause");
}
voidmain()//主界面
{
printf("课程设计---顶点间最短路径问题\n");
printf("物联网1303---龙安杰\n");
for(;;){
printf("1.问题描述\n");
printf("2.用Dijkstra求解\n");
printf("3.退出\n");
printf("请输入选择:");
charc;
intn;
c=getch();
intbz=1;
while(c!='\r')
{
n=0;
if(0x08==c)
{
printf("\b\b");
}
else
{
if(bz)bz=!bz;
elseprintf("\b");
switch(c)
{
case'1':printf("1");break;
case'2':printf("2");break;
case'3':printf("3");break;
default:printf("%c",c);break;
}
n=c-'0';
}
c=getch();
}
//printf("%d",n);//测试
switch(n)
{
case1:ShowProblem();break;
case2:Shortest_DIJ();break;
case3:return;
default:printf("\bError,Pressanykeytoenteragain!");getch();
}}
}
分 -->
|