I need to find the shortest path between 2 points in a Graph

This task must be done in C language

I chose to use Dijkstra's algorithm to solve this problem. When working with 442 vertexes, I instantly find the path with no problems, however, when working with 6111 and 12605 (teacher's test cases), the algorithm begins to slow down so much at the point that it takes 8 minutes to find one single path.

My graph implementation works with adjacent lists to prevent n^2 size.

The Dijkstra that I implemented was based in ComputerPhile's video https://www.youtube.com/watch?v=GazC3A4OQTE, using priority queue, with a while(current_vertex != destination && get_size(priority_queue) > 0), also the priority of each node on the priority queue is calculated using street_length or street_length/average_speed.

Because of the vertexes are on a plane, I tried doing a A* adaptation adding to the cost of each node from the priority queue the Euclidian distance between the current vertex position, and the destination vertex.

The Code

EDIT: Optimized with one 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;
        
}

So far, I've done this. I think it's slow because of the priority of a lot of cases is very close. Is there any suggestion to optimize more this 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;

}

CodePudding user response：

Problem solved with a if(find_element(visited_vertexes, search, compare) == NULL) before starting the analysis of the current vertex. This prevents that an already visited and analyzed vertex is inserted again, on the priority queue.