最短路径问题，课程设计遇到麻烦了，在线等大侠
明天就要交课程设计了，我的项目是最短路径实现弗洛伊德算法和迪杰斯特算法。在网上看到这篇代码 我修改了N天 都运行不了。 大侠们，救我啊！！！！[tk09]#include"iostream.h"
#define TRUE 1
#define FLASE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
//============ADT Stack 的表示与实现==========
//---------栈的顺序存储表示----------
//#include"constdefine.h"
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
//typedef char SElemType;
typedef char SElemType;
typedef struct {
SElemType *base;
SElemType *top;
SElemType stacksize;
}SqStack;
//-----------基本操作的函数原型说明---------
Status InitStack(SqStack &S);
//构造一个空栈S
Status DestroyStack(SqStack &S);
//销毁栈S,S不存在
Status StackEmpty(SqStack S);
//判断栈为空栈，则返回1，否则返回0
Status Push(SqStack &S,SElemType e);
//插入新的元素进栈
Status Pop(SqStack &S,SElemType &e);
//若栈顶空则返回0，不空删除栈顶元素，并返回到e中
SElemType GetTop(SqStack S,SElemType &e);
//返回栈顶的元素，
//---------基本的算法描述----------
//#include"ADTstack.h"
Status InitStack(SqStack &S){
//构造一个空栈
S.base=new SElemType[100];
if(!S.base) return OVERFLOW;
S.top=S.base;
S.stacksize=10;
return OK;
}
Status StackEmpty(SqStack S){
if(S.top==S.base) return TRUE;
else return FLASE;
}
Status DestroyStack(SqStack &S)
{
delete[] S.base;
return OK;
}
Status Push(SqStack &S,SElemType e){
if(S.top-S.base>=S.stacksize)
{
S.base=new SElemType[10+S.stacksize];
if(!S.base) return OVERFLOW;
S.top=S.base+S.stacksize;
S.stacksize+=10;
}
*S.top++=e;
return OK;
}
Status Pop(SqStack &S,SElemType &e){
if(S.top==S.base) return ERROR;
e=*--S.top;
return OK;
}
SElemType GetTop(SqStack S)
{
SElemType* p=S.top;
return *p--;
}
//#include"constdefine.h"
/*#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;*/
#define INFINITY 32767
#define MAX_VERTEX_NUM 20
typedef char VertextType;
typedef int PathMatrix;
typedef int ShorPathTable;
typedef int VRType;
typedef int DistancMatrix;
typedef struct{
VertextType vexs[MAX_VERTEX_NUM];//顶点向量
VRType arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//邻接矩阵
int vexnum,arcnum;//图的顶点数和弧数
}MGraph;
Status CreateDN(MGraph &G){
int LocateVex(MGraph,VertextType);
int i,j,k;
VRType w;
VertextType a,b;
cout<<"输入顶点数和弧数:例如 3 5"<<endl;
cin>>G.vexnum>>G.arcnum;
cout<<"请输入顶点信息：例如 a b c"<<endl;
for(i=0;i<G.vexnum;i++)//构造顶点向量
cin>>G.vexs[i];
for(i=0;i<G.vexnum;i++)//初始化邻接矩阵
for(j=0;j<G.vexnum;j++){
if(i==j) G.arcs[i][j]=i;
G.arcs[i][j]=INFINITY;
}
cout<<"输入边的两个顶点及其权值:例如 a b 4 再回车；"<<endl;
for(i=0;i<G.arcnum;i++){
cin>>a>>b>>w;
j=LocateVex(G,a);
k=LocateVex(G,b);
G.arcs[j][k]=w;
}
return OK;
}
int LocateVex(MGraph G,VertextType u){
int i;
for(i=0;i<G.vexnum;i++)
if(G.vexs[i]==u)
break;
return i;
}
int FirstAdjVex(MGraph G,VertextType u){//返回u的第一个邻接点在图中的位置
int i,j;
i=LocateVex(G,u);
for(j=0;j<G.vexnum;j++)
if(G.arcs[i][j]<INFINITY)
return j;
return -1;
}
int NextAdjVex(MGraph G,VertextType v,VertextType w){//返回v的(相对于w的)下一个顶点
int i,j,k;
i=LocateVex(G,v);
j=LocateVex(G,w);
for(k=j+1;k<G.vexnum;k++)
if(G.arcs[i][k]<INFINITY)
return k;
return -1;
}
Status VisitFunc(MGraph G,int v){
cout<<G.vexs[v]<<endl;
return OK;
}
int visited[MAX_VERTEX_NUM ];
void DFSTraverse(MGraph G){//深度优先搜索
int i;
void DFS(MGraph,int);
for(i=0;i<G.vexnum;i++)
visited[i]=0;
for(i=0;i<G.vexnum;i++)
if(!visited[i])
DFS(G,i);
}
void DFS(MGraph G,int v){
int w;
visited[v]=1;
VisitFunc(G,v);
w=FirstAdjVex(G,G.vexs[v]);
while(w>=0){
if(!visited[w]){
v=w;
DFS(G,v);
}
w=NextAdjVex(G,G.vexs[v],G.vexs[w]);
}
}
void ShortestPath_FLOYD_my(MGraph G,PathMatrix P[MAX_VERTEX_NUM][MAX_VERTEX_NUM],DistancMatrix D[MAX_VERTEX_NUM][MAX_VERTEX_NUM]){
//用Floyd算法求有向网中各对顶点之间的最短路径之改进版
int v,w,u;
for(v=0;v<G.vexnum;v++)//初始化各对顶点之间路径及距离
for(w=0;w<G.vexnum;w++){
D[v][w]=G.arcs[v][w];
if(D[v][w]<INFINITY){
P[v][w]=v; //初始化各队中的前一个顶点，例如本例中p[1][0]的前一个顶点就是1；
}
}
for(u=0;u<G.vexnum;u++)
for(w=0;w<G.vexnum;w++)
for(v=0;v<G.vexnum;v++) //寻求最小路径;
if(D[v][w]>D[v][u]+D[u][w]){
D[v][w]=D[v][u]+D[u][w];
P[v][w]=u;
//当二者之间有比较小的路径,就把p[v][w]的前一个顶点修改;如p[0][2]之间有路径1,所以修改p[0][2]=1;
}
}
void ShortestPath_DIJ_my(MGraph G,int v0,PathMatrix p[MAX_VERTEX_NUM],ShorPathTable d[MAX_VERTEX_NUM]){
//求源点到各顶点的最短路径
int i,j,k,l;
int *final;
final=new int[G.vexnum];
for(i=0;i<G.vexnum;i++){
d[i]=G.arcs[v0][i];
final[i]=0;
if(d[i]<INFINITY) p[i]=v0;//初始化，p[i]前的一个点为顶点；
}
d[v0]=0;
final[v0]=1;
for(i=1;i<G.vexnum;i++){//主循环
int min=INFINITY;
for(j=0;j<G.vexnum;j++)//求当前最短路径
if(!final[j])
if(d[j]<min)
{
min=d[j];
k=j;
}
final[k]=1;
for(j=0;j<G.vexnum;j++)//更新当前最短路径及其距离
if(!final[j]&&min+G.arcs[k][j]<d[j])
{
d[j]=d[k]+G.arcs[k][j];
p[j]=k;
}//if
}//for
}
void main(){
int i,j,P[MAX_VERTEX_NUM][MAX_VERTEX_NUM],D[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
int p[MAX_VERTEX_NUM],d[MAX_VERTEX_NUM];
MGraph G;
CreateDN(G);
cout<<"===============输出邻接矩阵================="<<endl;
for(i=0;i<G.vexnum;i++){
for(j=0;j<G.vexnum;j++)
{
cout.width(8);
cout<<G.arcs[i][j]<<" ";
}
cout<<endl;
}
cout<<"=================顶点信息==================="<<endl;
DFSTraverse(G);
ShortestPath_FLOYD_my(G,P,D);
ShortestPath_DIJ_my(G,0,p,d);
SqStack S,S2;
SElemType e,x,v,w;
cout<<"==============弗洛伊德算法================="<<endl;
InitStack(S); //我们用栈的结构特点--先进后出把他们的顶点递归的存储;
for(v=0;v<G.vexnum;v++)
for(w=0;w<G.vexnum;w++)
{
if(w!=v)
{
cout<<G.vexs[v]<<"---->"<<G.vexs[w]<<endl; //输出路径;
x=w; //在递归之前先把x初始为终点;
while(x!=v)
{
Push(S,P[v][x]);
x=P[v][x]; //进栈,再进行递归;
}
while(!StackEmpty(S))
{
Pop(S,e);
cout<<G.vexs[e]; //出栈;
}
cout<<G.vexs[w]; //输出终点;
cout<<endl;
}
}
cout<<"===============迪杰斯特算法================"<<endl;
InitStack(S2);
for(w=0;w<G.vexnum;w++)
{
if(w!=0)
{
cout<<G.vexs[0]<<"---->"<<G.vexs[w]<<endl; //输出路径;
x=w;
while(x!=0)
{
Push(S2,p[x]);
x=p[x];
}
while(!StackEmpty(S2))
{
Pop(S2,e);
cout<<G.vexs[e]; //出栈;
}
cout<<G.vexs[w]; //输出终点;
cout<<endl;
}
}
}
页:
[1]