struct MyStack
{
int stack[50];//栈
int jl;//距离
};
//迪杰斯特拉算法
MyStack Dijkstra(map Map, int d, int e)//d设为起点,e设为终点
{
int stack[50] = { 0 }, id1 = 0;
int stackdata[50] = { 0 }, id2 = 0;
int stackfindlj[50][50] = { 0 }, id3 = 0;//路径保存
int stackfindjl[50] = { 0 };//距离保存
int isfind = 0;
for (int i = d; i < d + 1; i++)
{
for (int j = i; j < 12; j++)
{
int edge[12][12] = { 0 };//辅助地图
if (Map.edge[i][j] != 100 && Map.edge[i][j] != 0 && edge[i][j] == 0)
{
stack[id1++] = j;
stackdata[id2++] = Map.edge[i][j];//边的距离
edge[i][j] = 1;//辅助地图
while (id1)
{
for (int k = stack[id1 - 1]; k < 12; k++)
{
if (Map.edge[stack[id1 - 1]][k] != 100 && Map.edge[stack[id1 - 1]][k] != 0 && edge[stack[id1 - 1]][k] == 0)//开始搜寻路径
{
edge[stack[id1 - 1]][k] = 1;
stackdata[id2++] = Map.edge[stack[id1 - 1]][k];
stack[id1++] = k;
if (k == e)//到达了终点
isfind = 1;
break;
}
if (k == 11)
{
id1--; id2--;
}
}
if (isfind == 1)
{
stackfindlj[id3][0] = i + 1;
for (int k = 0; k < id1; k++)
{
stackfindlj[id3][k + 1] = stack[k] + 1;
stackfindjl[id3] += stackdata[k];
}
id3++;
isfind = 0;
}
}
}
}
}
int min = stackfindjl[0], minidx = 0;
for (int i = 0; i < id3; i++)
{
if (min > stackfindjl[i])
{
min = stackfindjl[i];
minidx = i;
}
}
MyStack temp = { 0 };
memcpy(&temp.stack, &stackfindlj[minidx], sizeof(int) * 50);//将得到的最短路径复制到结构体的数组之中
temp.jl = min;//将得到的最短距离赋值到结构体的距离中
printf("最短路径距离为:%d\n", temp.jl);
return temp;
只会输出最短距离
迪杰斯特拉函数
这是一个实现迪杰斯特拉算法的代码,用于求解单源最短路径问题。该算法是一种贪心算法,每次求解的时候都会找到当前能到达的点中距离起点最近的点,并从该点开始搜索下一步能到达的点,直到到达终点。
具体来说,代码中使用了三个栈:
1、stack 栈用来存储搜索路径中的点。
2、stackdata 栈用来存储每条边的距离。
3、stackfindlj 栈用来存储所有可能的路径,其中的每一行都是一条路径,第一个元素为起点,其余的元素为路径中的每个点。
首先,从起点开始搜索,如果找到了一条边且这条边还没有访问过,就将这条边加入路径中,并将这条边的距离加入路径距离中。然后从这条边的终点开始继续搜索,如果能找到一条边且这条边还没有访问过,就将这条边加入路径中,并将这条边的距离加入路径距离中。重复这个过程直到到达终点,或者找不到新的边可以加入路径中。
所有的路径被保存在 stackfindlj 中,其中的每一行都是一条路径。接下来,遍历所有的路径,找到路径距离最小的路径。将这条最短路径的信息复制到一个名为 temp 的结构体中,并返回这个结构体。
这个结构体中包含两个信息:
1、stack 数组用来存储最短路径中的点。
2、jl 变量用来存储最短路径的距离。
如果想输出最短路径的途径点信息,可以在输出路径距离之后添加以下代码:
printf("最短路径为:");
for (int i = 0; i < 50; i++) {
if (temp.stack[i] != 0) {
printf("%d ", temp.stack[i]);
}
}
printf("\n");
这段代码会依次输出最短路径中的所有点。
仅供参考,望采纳,谢谢。