除A*外Dijkstra算法优化方案：C语言大点数图最短路径性能问题

本任务必须使用C语言完成 #

我选择使用Dijkstra算法解决该问题。处理442个顶点的图时可以秒出路径，但处理老师给出的6111和12605顶点的测试用例时，算法运行速度大幅下降，单条路径查询耗时可达8分钟。
我的图采用邻接表实现，避免了O(n²)的空间占用。
我实现的Dijkstra算法使用了优先级队列，循环条件为while(current_vertex != destination && get_size(priority_queue) > 0)，优先级队列中每个节点的优先级通过路段长度或路段长度/平均速度计算。
由于顶点都位于平面上，我尝试做了A*适配，将当前顶点与目标顶点的欧氏距离加到优先级队列对应节点的成本中。

编辑：新增一个if语句做了优化

while(search != destination) {
        if(find_element(visited_vertexes, search, compare) == NULL) { //新增的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)); 
                    }
                }
            }
        }
        back_track = search; // 更新用于和下一个顶点比对
        helper* top = priority_queue_pop(prior_queue, false, free_helper);
        insert_list(visited_vertexes, top); // 更新已访问顶点，从优先级队列移除
        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;
}

目前我只做了这些优化，我认为运行慢的原因是很多节点的优先级非常接近。请问除了A*算法之外，还有哪些可以进一步优化Dijkstra算法的建议？

附：

typedef struct helper{
    void* vertex; //当前顶点
    void* from; //来源顶点
    double cost; //到当前节点的累计成本
} 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;
}

优化建议 #

• 替换已访问集合的存储结构
  你当前用普通链表存储已访问节点，find_element操作是O(n)时间复杂度，顶点数过万时这部分会成为核心瓶颈。如果顶点ID是连续整数，直接开布尔数组标记访问状态，查询O(1)；如果ID不连续，改用哈希表存储已访问节点，查询耗时也能降到近似O(1)。邻接节点的已访问判断同理，这一步优化就能把性能提升几个数量级。
• 优化优先级队列实现
  如果你的优先级队列是用数组或链表实现的，插入、取最值操作都是O(n)，万级顶点下开销极高。改用二叉堆实现优先级队列，插入和弹出操作都是O(logn)，能大幅降低队列操作的耗时。另外新增距离数组存储每个节点当前已知的最小成本，新计算出的邻接节点成本如果大于已存储的最小成本，直接跳过插入队列，减少堆中的无效元素数量。
• 优化启发值计算
  distance_dijkstra计算欧氏距离时的开方操作开销很高，A*的启发函数只要满足一致性，直接用欧氏距离的平方作为启发值即可，省掉开方运算。也可以提前预存所有顶点的坐标到数组里，计算时直接索引取值，避免每次额外查询结构体的开销。
• 减少动态内存分配开销
  你每次插入队列都调用calloc新建helper对象，上万次动态内存分配+后续释放的开销非常大。可以提前预分配内存池存储helper对象，或者直接把前驱节点、当前最小成本的字段加到顶点结构体里，不需要额外生成helper对象，完全省掉malloc/free的耗时。
• 增加剪枝逻辑
  A*算法满足启发函数可采纳性的前提下，第一次弹出目标顶点时就可以直接终止循环，不需要等队列空。另外如果当前节点的优先级（累计成本+启发值）已经大于当前已知的到目标点的最短路径，直接跳过处理该节点。
• 缓存友好优化
  邻接表的节点尽量按内存连续存储，不要每个节点单独malloc，遍历时CPU缓存命中率更高，能进一步提升运行速度。

内容的提问来源于stack exchange，提问作者Kresnik