一张地图包括n个城市,假设城市间由m跳路径(有向图),每条路径的长度已知,给定地图的一个起点城市和终点城市,利用Dijsktra算法求出起点到重点之间的最短路径。
函数接口定义:
在这里描述结构体和函数接口:
#include <iostream>
using namespace std;
#define ERROR 0
#define MaxInt 32767 //表示极大值,即∞
#define MVNum 100 //最大顶点数
typedef char VerTexType; //假设顶点的数据类型为字符型
typedef int ArcType; //假设边的权值类型为整型
int *D=new int[MVNum]; //用于记录最短路的长度
bool *S=new bool[MVNum]; //标记顶点是否进入 S 集合
int *Path=new int[MVNum]; //用于记录最短路顶点的前驱
//图
typedef struct
{
VerTexType vexs[MVNum]; //顶点表
ArcType arcs[MVNum][MVNum]; //邻接矩阵
int vexnum,arcnum; //网的当前点数和边数
} AMGraph;
//显示从起点到终点的最短路径
void DisplayPath(AMGraph G, int begin,int end );
int LocateVex(AMGraph G, VerTexType v);
//创建有向网的邻接矩阵
void CreateUDN(AMGraph &G);
//显示图的邻接矩阵
void DisplayG(AMGraph G);
//计算从v0起点的最短路径
void ShortestPath_DJI(AMGraph G,int v0);
裁判测试程序样例:
在这里给出函数被调用进行测试的例子,mode控制测试的不同函数:
int main()
{
AMGraph G;
VerTexType start,destination;
int mode;
cin>>mode;
CreateUDN(G);
int num_start,num_destination;
cin >> start >> destination;
//计算起点与终点编号
num_start = LocateVex(G, start);
num_destination = LocateVex(G, destination);
ShortestPath_DJI(G,num_start);//调用函数求最短路径
switch(mode)
{
case 1: DisplayG(G);break;
case 2: cout<<num_start<<" "<<num_destination<<endl;
break;
case 3: cout<<start<<"->"<<destination<<" length:"<<D[num_destination]<<endl;
break;
case 4: cout<<start<<"->"<<destination<<endl;
cout <<"Shortest Path:";
DisplayPath(G, num_start, num_destination);
cout << G.vexs[num_destination]<<endl;
}
return 0;
}
/* 请在这里填写答案 */
输入样例1:
在这里给出一组输入,第一行是mode的值,代表测试的不同函数,第二行是两个整数n和m,分别代表城市个数和路径条数,第三行有n个字符,代表城市的名称。接着是m行的数据,每一行有两个字符a和b以及一个整数d,代表从城市a到城市b有一条距离为d的路,最后一行为两个字符,代表待求最短路径得城市起点和终点。
1
3 3
A B C
A B 1
B C 1
C A 3
A C
输出样例1:
在这里给出相应的输出,当mode为1,显示创建好的邻接矩阵,不可达的无穷大值显示为字符'∞'(程序中可拷贝本字符),其余显示为有效值,数据之间用逗号分隔。当mode为4,显示从起点到终点的最短路径,城市时间用箭头相隔;其余mode为2,3的显示见测试程序:
∞,1,∞
∞,∞,1
3,∞,∞
输入样例2:
在这里给出一组输入,第一行是mode的值,代表测试的不同函数,第二行是两个整数n和m,分别代表城市个数和路径条数,第三行有n个字符,代表城市的名称。接着是m行的数据,每一行有两个字符a和b以及一个整数d,代表从城市a到城市b有一条距离为d的路,最后一行为两个字符,代表待求最短路径得城市起点和终点。
4
3 3
A B C
A B 1
B C 1
C A 3
A C
输出样例2:
在这里给出相应的输出,当mode为1,显示创建好的邻接矩阵,不可达的无穷大值显示为字符'∞'(程序中可拷贝本字符),其余显示为有效值,数据之间用逗号分隔。当mode为4,显示从起点到终点的最短路径,城市时间用箭头相隔;其余mode为2,3的显示见测试程序:
A->C
Shortest Path:A->B->C
我的答案
int LocateVex(AMGraph G, VerTexType v){
int i;
for(i=0;i<G.vexnum;i++){
if(v==G.vexs[i])return i;
}return -1;
}
void CreateUDN(AMGraph &G){
VerTexType v1,v2;
ArcType w;
int i,j,k;
cin>>G.vexnum>>G.arcnum;
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++)
G.arcs[i][j]=MaxInt;
for( k=0;k<G.arcnum;k++){
cin>>v1>>v2>>w;
i=LocateVex(G, v1);
j=LocateVex(G, v2);
G.arcs[i][j]=w;
}
}
void DisplayG(AMGraph G){
int j,k;
for(j=0;j<G.vexnum;j++)
for(k=0;k<G.vexnum;k++){
if(k!=G.vexnum-1){
if(G.arcs[j][k]!=MaxInt)
cout<<G.arcs[j][k]<<",";
else cout<<"∞"<<",";
}
else{
if(G.arcs[j][k]!=MaxInt)
cout<<G.arcs[j][k]<<endl;
else cout<<"∞"<<endl;
}
}
}
void ShortestPath_DJI(AMGraph G,int v0){
int v=0;
int n=G.vexnum;
int min,i,w;
for(v;v<n;v++){
S[v]=false;
D[v]=G.arcs[v0][v];
if(D[v]<MaxInt)Path[v]=v0;
else Path[v]=-1;
}
S[v0]=true;
D[v0]=0;
for(i=0;i<n;++i){
min= MaxInt;
for( w=0;w<n;++w)
if(!S[w]&&D[w]<min){
v=w;
min=D[w];
}
S[v]=true;
for( w=0;w<n;++w)
if(!S[w]&&(D[w]+G.arcs[v][w]<D[w])){
D[w]=D[v]+G.arcs[v][w];
Path[w]=v;
}//if
}
}
void DisplayPath(AMGraph G , int begin ,int end ){
if(Path[end] != -1){
DisplayPath(G , begin ,Path[end]);
cout << G.vexs[Path[end]] << "->";
}
}
最后一个函数一直错误,但是我看不出来,希望可以指教一下,或者有代码参考一下