| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 933 人关注过本帖
标题:最短路径问题,课程设计遇到麻烦了,在线等大侠
取消只看楼主 加入收藏
yaoxlong1031
Rank: 1
等 级:新手上路
帖 子:2
专家分:0
注 册:2008-6-19
收藏
 问题点数:0 回复次数:0 
最短路径问题,课程设计遇到麻烦了,在线等大侠
明天就要交课程设计了,我的项目是最短路径实现弗洛伊德算法和迪杰斯特算法。在网上看到这篇代码 我修改了N天 都运行不了。 大侠们,救我啊!!!!


#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;
  }
 }


   

}
搜索更多相关主题的帖子: define 课程 路径 弗洛伊德 
2008-06-19 16:10
快速回复:最短路径问题,课程设计遇到麻烦了,在线等大侠
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.032417 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved