除了使用 A* 之外，还有其他优化 Dijkstra 算法的方法吗？

Question

我需要找到图中两点之间的最短路径

这个任务必须用C语言完成

我选择用Dijkstra的算法来解决这个问题。当处理 442 个顶点时，我立即找到没有问题的路径，但是，当处理 6111 和 12605（老师的测试用例）时，算法开始变慢，以至于需要 8 分钟才能找到一条路径.

我的图形实现与相邻列表一起使用以防止 n^2 大小。

我实现的Dijkstra是基于ComputerPhile的视频https://www.youtube.com/watch?v=GazC3A4OQTE，使用优先级队列，有一个while(current_vertex != destination && get_size(priority_queue) > 0)，优先级队列中每个节点的优先级是使用[=40=计算的] 或 street_length/average_speed.

因为顶点在一个平面上，我尝试做一个 A* 自适应添加到每个节点的成本优先队列当前顶点位置和目标顶点之间的欧几里得距离。

代码

编辑：优化了一个 if

while(search != destination) {

        if(find_element(visited_vertexes, search, compare) == NULL) { //Added this if

            void* search_adjacents = list_of_adjacents_by_address(search);

            for(void* aux = get_head(search_adjacents); aux; aux = get_next(aux)){

                void* edge = get_list_element(aux);

                if(edge_get_from(edge) != edge_get_to(edge)) {

                    void* edge_data = edge_get_data(edge);
                    void* edge_to = edge_get_to(edge);

                    double cost_until_this_point = operation_mode(edge_data) + search_cost;
                    
                    void* found = find_element(visited_vertexes, edge_to, compare);

                    if(found == NULL && edge_to != back_track) {

                        priority_queue_insert(prior_queue, new_helper(edge_to, search, cost_until_this_point + distance_dijkstra(edge_to, destination)), cost_until_this_point + distance_dijkstra(edge_to, destination)); // Are we able to use a* ?

                    }

                }
                
            }

        }

        back_track = search; // Update to compare with the next vertex

        helper* top = priority_queue_pop(prior_queue, false, free_helper);

        insert_list(visited_vertexes, top); // Updated visited vertexes, remove from the priority queue

        helper* next_vertex = priority_queue_get_element(priority_queue_get_head(prior_queue));

        if(!next_vertex) break;

        search = next_vertex->vertex;
        search_cost = next_vertex->cost;
        
}

到目前为止，我已经做到了。我认为它很慢，因为很多案例的优先级非常接近。有什么建议可以优化这个 Dijkstra 吗？

P.S:


typedef struct helper{

    void* vertex; //Current vertex
    void* from; //Where it came from
    double cost; //Cost until here

} helper;

void* new_helper(void* vertex, void* from, double cost) {

    helper* aux = calloc(1, sizeof(helper));
    aux->vertex = vertex;
    aux->from = from;
    aux->cost = cost;

    return aux;

}

Answer 1

在开始分析当前顶点之前用 if(find_element(visited_vertexes, search, compare) == NULL) 解决了问题。这可以防止在优先级队列中再次插入已经访问和分析的顶点。

除了使用 A* 之外，还有其他优化 Dijkstra 算法的方法吗？

Is there a way of optimizing Dijkstra algorithm other than using A*?

c

algorithm

dijkstra

a-star

我需要找到图中两点之间的最短路径

这个任务必须用C语言完成

代码