以下的c＋＋程序是在数据结构课上做的Dijkstra的算法
你要是可以看明白在修改一点（其实就是向程序里加那题的数据）就可以直接用了
导出的数据存在e:\out.txt里（这个你可以根据你自己的喜好再改）
/*
Name: Shortest Path Used DJ
Author: Ran Ni
Description: Shortest Path Used DJ and the graph is saved in Crosslist.
Date: 07-06-03 18:09
Copyright: Ran Ni
*/
#include <iostream.h>//输入输出流头文件
#include <fstream.h>//文件流头文件
#define M 10//图的最大节点数
#define N 1000000//定义一个很大的数作为比较旗帜
struct path{
int data;
path *next;
};
struct cnode{//十字链表中的存储图中边的节点
int i,j;//节点所在的行和列，行列数组中的该数据存储节点的出度和入度
int weight;//边的权重
int dele;//标记的变量
cnode *right;
cnode *down;
};
struct graph{//存储图的结构体
int num;//图中的节点数
cnode row[M];//行数组
cnode vol[M];//列数组
int edge;//图中边的数目
};
ofstream out("e:\\out.txt");
void add(graph *g,int i,int j,int weight)//添加图中的边起点终点和权值分别为i,j和weight
{ cnode *p,*q;
q=new cnode;//申请空间存储新的边
q->i=i;
q->j=j;
q->weight=weight;
q->right=NULL;//指针初始化
q->down=NULL;
q->dele=0;//表示该边没有被删除
p=&(g->row);
p->dele=0;
g->vol.dele=1;//dele为1表示该节点没有被删除
if(!p->right)//如果该节点所在行没有节点,直接添加
{ p->right=q;
}else if(p->right->j>j)//如果该节点所在行的第一个已有的节点所在列比该节点大,将其添加在第一个节点之前
{ q->right=p->right;
p->right=q;
}else if(p->right->j==j)//如果该节点已经存在,将其覆盖
{ p->weight=q->weight;
}else if(p->right->j<j)//如果该节点所在行的第一个已有的节点所在列比该节点小,需要寻找合适的位置添加该节点
{ while(!((p->right==NULL)||((p->j<j)&&(p->right->j>j))||(p->j==j)))//三个可能添加的位置
{ p=p->right;
}
if(p->right==NULL)//当应该将其添加在所在行的最后一个时
{ p->right=q;
}
else if((p->j<j)&&(p->right->j>j))//当应该将其添加在某两个节点之间时
{ q->right=p->right;
p->right=q;
}else if(p->j==j)//当该节点已经存在时
{ p->weight=q->weight;
}
}
g->row.i++;//图中第i个节点的出度加1
g->vol.i++;
p=&(g->vol[j]);//以下为将该节点进行对列添加进行类似的操作
p->dele=0;
g->row[j].dele=1;
if(!p->down)
{ p->down=q;
}else if(p->down->i>i)
{ q->down=p->down;
p->down=q;
}else if(p->down->i==i)
{ p->weight=q->weight;
}else if(p->down->i<i)
{ while(!((p->down==NULL)||((p->i<i)&&(p->down->i>i))||(p->i==i)))
{ p=p->down;
}
if(p->down==NULL)
{ p->down=q;
}
else if((p->i<i)&&(p->down->i>i))
{ q->down=p->down;
p->down=q;
}else if(p->i==i)
{ p->weight=q->weight;
}
}
g->vol[j].j++;//图中第j个节点的入度加1
g->row[j].j++;
g->edge++;
}
/*
viod change(path *,path *q,int,int)
p,q分别指向存储start节点到q->data节点和p->data节点的最短路径的链表的头节点
n为边的终点,data为新添加的边的权值
本函数的作用是将q的链表深拷贝到p(首先将链表p销毁),再在p最后加一个新边data(终点为n)
*/
void change(path *p,path *q,int n,int data)
{ path *r=p;
while(r->next)//销毁链表p
{ r=p;
while(r->next->next)
{ r=r->next;
}
delete r->next;
r->next=NULL;
}
r=p;
path *t=q;
while(t->next)//拷贝q到p
{ t=t->next;
r->next=new path;
r=r->next;
r->data=t->data;
r->next=NULL;
}
p->data=q->data+data;//在最后添加新边
r->next=new path;
r->next->data=n;
r->next->next=NULL;
}
/*
打印起点start到终点end的最短路径(其链表存在p中)
*/
void print(int start,int end,path *p)
{ if(p->data!=N)//如果start到end存在最短路径,打印p所指向的链表
{ cout<<"\nThe shortest distance of the"<<start<<"th"<<" node "<<"between the "<<end<<"th node is "<<p->data<<endl;
out<<"\nThe shortest distance of the"<<start<<"th"<<" node "<<"between the "<<end<<"th node is "<<p->data<<endl;
cout<<"The path is:"<<endl;
out<<"The path is:"<<endl;
while(p->next)//打印路径
{ p=p->next;
cout<<p->data<<" ";
out<<p->data<<" ";
}
}
else//当不存在start到end的最短路径时,打印没有最短路径,即不可达
{ cout<<"\nThere is no path from the "<<start<<"th node to the "<<end<<"th node.";
out<<"\nThere is no path from the "<<start<<"th node to the "<<end<<"th node.";
}
}
/*
求图g中从start到其余各个节点的最短路径,用DJ算法.
*/
void Shortestpath_Dj(graph *g,int start)
{ path dis[g->num];//创建所有存储节点最短路径的链表的头节点(头节点存储最短路径长度,以后的节点存储路径)
for(int i=0;i<g->num;i++)//初始化标记和长度
{ g->row.dele=0;
g->vol.dele=0;
dis.data=N;
dis.next=new path;
dis.next->next=NULL;
dis.next->data=start;
}
dis[start].data=0;//初始化start节点的路径链表
g->row[start].dele=1;
g->vol[start].dele=1;
cnode *p=&(g->row[start]);
while(p->right)//寻找可以和start节点直接有关系(即有边)的节点,并标记他们
{ p=p->right;
dis[p->j].data=p->weight;
dis[p->j].next->next=new path;
dis[p->j].next->next->data=p->j;
dis[p->j].next->next->next=NULL;
g->row[p->j].dele=1;
g->vol[p->j].dele=1;
}
for(int k=0;k<g->num;k++)//循环查找图中的节点g->num次
{ for(int i=0;i<g->num;i++)//遍历图中的节点
{ p=&(g->vol);
while(p->down)//当有边指向他时,判断指向他的节点中是否有已经被标记的
{ p=p->down;
if(g->row[p->i].dele==1)//当存在已经标记过的节点指向他时,标记该节点
{ g->row.dele=1;
g->vol.dele=1;
if(dis[p->i].data+p->weight<dis.data)//如果该指向他的节点的最短路径长度加上他们之间的边的权值,则调用change函数
{ change(&(dis),&(dis[p->i]),i,p->weight);
}
}
}
}
}
for(int i=0;i<g->num;i++)//打印start节点到所有节点的最短路径和最短路径长度
{ if(i!=start)
{ print(start,i,&(dis));
}
}
}
void main()
{ graph *g=new graph;//申明一个图的指针,并对其分配空间
int start;
g->edge=0;
for(int i=0;i<M;i++)//变量初始化
{ g->row.right=NULL;
g->row.down=NULL;
g->row.i=0;
g->row.j=0;
g->row.weight=0;
g->row.dele=0;
g->vol.right=NULL;
g->vol.down=NULL;
g->vol.i=0;
g->vol.j=0;
g->vol.weight=0;
g->vol.dele=0;
}
cout<<"*******************************************************"<<endl;
cout<<" Shortest Path_DJ"<<endl;
cout<<"*******************************************************"<<endl;
cout<<"Input the number of the node in the graph:"<<endl;
cin>>g->num;//读入图中所拥有的节点数
step1:cout<<"Input the start node of the edge:"<<endl;
int i;
cin>>i;//读入边的起点
cout<<"Input the end node of the edge:"<<endl;
int j;
cin>>j;//读入边的终点
if((i>g->num-1)||(j>g->num-1))//判断是否输入出错
{ cout<<"Input error!"<<endl;
goto step1;
}
cout<<"Input the weight of the edge:"<<endl;
int weight;
cin>>weight;//读入边权
add(g,i,j,weight);
out<<"("<<i<<","<<j<<","<<weight<<")"<<endl;
step2:cout<<"Is there any other edge?(y/n)"<<endl;//判断是否还有其他节点
char c;
cin>>c;
if(c=='y')
{ goto step1;
}else if((c!='y')&&(c!='n'))
{ cout<<"Input error!"<<endl;
goto step2;
}
step3:cout<<"Input the start node"<<endl;
cin>>start;//读入等待计算的start节点
if(start>g->num-1)//判断是否输入出错
{ cout<<"Input error!"<<endl;
goto step3;
}
Shortestpath_Dj(g,start);//求start到图g中其他各节点的最短路径
step4:cout<<"\nWould you like to calculate another node?(y/n)"<<endl;//判断是否继续计算其他节点
char d;
cin>>d;
if(d=='y')
{ goto step3;
}else if((d!='y')&&(d!='n'))
{ cout<<"Input error!"<<endl;
goto step4;
}
}
|
发表于 2003-8-3 19:21:23
发表于 2003-8-5 23:31:06
楼主