Question

编一个C++程序，求最短路径

1. 选择15个以上你最熟悉的世博会场馆，并为该世博会导航系统建立相应的数据结构。例如：以每个场馆为节点，节点中记录该场馆的代号，名称，介绍信息等；用弧来表示道路，弧中记录该道路的代号，名称，以及道路的长度等相关信息。
2. 为游客提供建筑景点相关描述信息的查询。
a. 在DOS命令行提示符下，当游客输入景点的名称，会显示出介绍该景点的相关描述信息。如：
输入：中国馆（可用英文名）
输出：介绍中国馆的相应信息
3. 为游客提供任意景点的问路查询，即从一个景点到另一个景点的最短路径。
a. 在DOS命令行提示符下：
输入：景点A 景点B
输出：（景点A）->道路名称1->(景点C)->….->道路名称n->(景点B)

Answer 1

其实比较简单的，做个记号
path为邻接矩阵，begin end为起始，结束点 0<= begin end <= Maxsize
path->length 最短路径长度，Path->path[] 最短路顶点

typedef struct {
int length;
int path[Maxsize]; //记录路径
}Path;

Path *ShortPath(int path[][Maxsize],int N,int begin,int end) {
int i, j, k, start, temp, MinLength, last; //i,j,k,h：循环变量，length：路径长度,start:开始点,temp:临时变量,last:最后一个点,
int mark[Maxsize]; //记录最小值标点
int min[Maxsize][Maxsize]; //记录最短路径,节点
int t[Maxsize]; //记录min当前位置
Path *p;

p = (Path *)malloc(sizeof(Path)); //初始化p
p->length = -1;
p->path[0] = -1;
start = begin; //初始化Start
mark[start] = 1; //记录起始点为最小值标点
MinLength = Num;

for (i = 0;i < N;i++) { //初始化路径数组
for (j = 0;j < N;j++) {
if((i != j) && (path[i][j] <= 0))
path[i][j] = Num;
min[i][j+1] = -1;
}
min[i][1] = begin; //记录起始位
min[i][2] = i; //记录最后位
mark[i] = -1; //初始化min,mark,record
min[i][0] = path[start][i];
t[i] = 2;
}
for (i = 1;i <= N;i++) { //求最小值标点
MinLength = Num;
for (j = 0;j < N;j++) {
if (mark[j] == -1) {
temp = min[start][0] + path[start][j]; //求到j点的最短路径
if (temp >= min[j][0])
temp = min[j][0];
else {
t[j] = t[start] + 1;
min[j][t[j]] = j;
for (k = 2;k <= t[start];k++)
min[j][k] = min[start][k];
}
min[j][0] = temp;
if ((MinLength == temp) && (j != end) && (last == end)); //last固定在end位
if (MinLength >= temp) { //求，记录最小指标点
MinLength = temp;
last = j;
}
}
}
if (MinLength < Num) { //更新最短路径
start = last;
mark[start] = 1;
}
else
break;
if (start == end) { //判断最短路径输出
for(i = 1;i <= N;i++)
p->path[i-1] = min[end][i];
p->length = min[end][0];
break;
}
}
return p;
}

Answer 2

容量不很大的话，就把所有路径穷举出来排个序吧

Answer 3

比较常用的 A* 算法,网上找找.

Answer 4

100分很吸引人啊..不过这个... 有点难度，要我编的话加上调试没有一个星期是出不来的，呵呵，上CSDN应该能下到类似的。爱莫能助，祝你好运吧！