我需要找到圖表中兩點之間的最短路徑
這個任務必須用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)，并且優先佇列上每個節點的優先級也是使用 street_length 或 street_length/ 計算的平均速度。
由于頂點在一個平面上，我嘗試做一個A * 適應，將當前頂點位置和目標頂點之間的歐幾里得距離添加到優先佇列中每個節點的成本中。
編碼
編輯：優化一個如果
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 嗎？
PS：
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;
}
uj5u.com熱心網友回復：
if(find_element(visited_vertexes, search, compare) == NULL)在開始分析當前頂點之前用 a 解決了問題。這可以防止在優先級佇列中再次插入已經訪問和分析過的頂點。
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/369678.html
上一篇：在網格中找到第K個最小元素？