1

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;

}
Kresnik
  • 93
  • 1
  • 2
  • 9
  • 2
    Dijkstra's algorithm in C on a graph with 12605 vertices shouldn't take more than a few milliseconds even if it is very dense. You don't need a more complicated algorithm. You just need to fix your implementation. The problem doesn't seem to be in the code you've posted. – Matt Timmermans Nov 26 '21 at 02:15
  • I need to read the data from files, and that actually doesn't take more than 1~2 seconds, but the place where the code is slow is on this part of Dijkstra implementation. – Kresnik Nov 26 '21 at 02:27
  • 2
    You're calling a function `distance_dijkstra` in a loop, is this the Euclidean distance calculator or a full Dijkstra's algorithm? Also, if you're using your own custom priority queue, you should post that code as well. A different algorithm won't help if your priority queue implementaion has linear-time inserts, for example. – kcsquared Nov 26 '21 at 03:42
  • Every insertion into the priority queue involves dynamic memory allocation (in function `new_helper()`), which is slow. It seems doubtful that that accounts for minutes of run time, though. Most likely, the main problem is a suboptimal priority queue. – John Bollinger Nov 26 '21 at 04:14
  • _I think it's slow because of the priority_ consider [profiling](https://stackoverflow.com/questions/1794816/recommendations-for-c-profilers) – c0der Nov 26 '21 at 07:39
  • @kcsquared Yes, it searches for a node with a smaller priority, then it inserts on the priority queue, so I think it is linear-time inserts. – Kresnik Nov 26 '21 at 14:01
  • Have your tried `-Ofast -flto` ? – user426 Nov 26 '21 at 15:05
  • @c0der as an aside, i am looking for a CLI profiling tool for macOS, so neither `gprof` not Xcode will cut it. Any suggestions ? – user426 Nov 26 '21 at 15:07

1 Answers1

0

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.

Kresnik
  • 93
  • 1
  • 2
  • 9