gpt4 book ai didi

c - 在 C 问题中实现 Dijkstra 算法

转载 作者:行者123 更新时间:2023-12-04 12:00:41 31 4
gpt4 key购买 nike

我们一直在做一个机器人在房间里行驶的项目,当我们激活它时,它会返回到选定的目的地。我们的任务是找到到达目的地的最短路径。

我们一直在用 C 编写代码,并尝试使用 Dijkstra 算法,但我们现在有点卡住了。我们没有得到最短路线。weights中的第一个位置是起始坐标,end是最后一个。

double dijkstras(double weights[MAX_ARRAY_SIZE][MAX_ARRAY_SIZE], char output[], int     *output_number_of_waypoints, int number_of_waypoints){ 

double route_length[number_of_waypoints];
int shortest_route_via[number_of_waypoints];

int i, current_pos;
double distance;
for (i = 0; i < number_of_waypoints; i++) {
route_length[i] = 0;
shortest_route_via[i] = -1;
}

int start = 0; /* first index in array */
int end = number_of_waypoints-1; /* last index in array */

for (current_pos = start; current_pos <= end; current_pos++) {
for (i = 0; i < number_of_waypoints; i++) {
if (weights[current_pos][i] > 0) {
distance = route_length[current_pos] + weights[current_pos][i];
if (distance < route_length[i] || shortest_route_via[i] == -1) {
printf("shortest_route_via[%d] = current_pos = %d, length was %lf, shorted to %lf\n", i, current_pos, route_length[i], distance); /* debugging info */
route_length[i] = distance;
shortest_route_via[i] = current_pos;
}
}
}
}
current_pos = end;
i = 0;
char route[number_of_waypoints+1];
while (current_pos != start && i < number_of_waypoints) {
route[i] = current_pos;
printf("currentpos = %d\n", current_pos); /* Debugging info - shortest path */
current_pos = shortest_route_via[current_pos];
i++;
}
route[i] = '\0';

return route_length[end];

我们想要得到一个数组 - shortest_route_via,其中包含通过索引的最短路线 - 例如 shortest_route_via[index] = waypoint。Route_length 包含前往索引的成本,例如 route_length[index] = 100,表示前往索引的成本为 100。

希望有人能看到我们遗漏了什么。

最佳答案

如果我正确地解释了你的代码,那么你并不是真的在做 Dijkstra。

Dijkstra 从根节点开始,然后查看它可以到达的所有邻居。然后暂时设置从根到所有邻居的距离。在接下来的迭代中,临时设置的节点中最近的节点成为永久节点,并临时设置其邻居。

您的代码没有选择最近的节点。您只需通过递增 current_pos 来按节点 ID 的顺序遍历所有节点。除非最短路径严格按节点顺序递增(索引仅增加 1->4->10->14->...),否则您将无法获得有保证的最短路径。

关于c - 在 C 问题中实现 Dijkstra 算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13759316/

31 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com