3

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

我们一直在用 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。

希望有人能看到我们缺少的东西。

4

2 回答 2

3

如果我正确解释了您的代码，那么您实际上并没有在做 Dijkstra。

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

您的代码没有选择最近的节点。您只需按其 id 的顺序通过递增遍历所有节点current_pos。除非最短路径是严格按节点顺序递增的（索引只会像 1->4->10->14->... 一样增加），否则您将无法获得保证的最短路径。

于 2012-12-07T13:03:30.700 回答
0

我的博客上提供了针对此问题的更高效和完整的 c 代码。你可以免费得到她..... http://www.blogger.com/blogger.g?blogID=1775252317107864249#editor/target=post;postID=1976885424431604242;onPublishedMenu=allposts;onClosedMenu=allposts;postNum=0 ;src=邮件名

于 2012-12-26T04:48:10.363 回答