0

I was learning the dijkstra's algorithm and then in that there was the concept of priority queue with min_heap implementation where my priority_queue <Node,vector<Node>,comp> min_heap and the comp is a comparison struct;

struct Edge{
    int src;
    int dest;
    int weight;
};

struct Node{
    int vertex;
    int weight;
};

class Graph{
    public:
    vector<vector<Edge>> adjList;
    Graph(vector<Edge> &edges,int N){
        adjList.resize(N);
        for(auto &edge:edges){
            adjList[edge.src].push_back(edge);
        }
    }
};

struct comp{
    bool operator()(const Node &lhs,const Node &rhs) const{
        return lhs.weight>rhs.weight;
    }
};

void dij(Graph g,int source,int N){
    priority_queue<Node,vector<Node>,comp> min_heap;
    min_heap.push({source,0});
    vector<int> dist(N,INT_MAX);
    dist[source] = 0;
    vector<bool> done(N,false);
    done[0] = true;
    while(!min_heap.empty()){
        Node node = min_heap.top();
        min_heap.pop();
        int u = node.vertex;
        for(auto i:g.adjList[u]){
            int v = i.dest;
            int weight = i.weight;
            if(!done[u] && dist[u]+weight<dist[v]){
                dist[v] = dist[u] + weight;
                min_heap.push({v,dist[v]});
            }
        }
        done[u] = true;
    }
    cout<<"The path from vertex "<<source<<" to "<<N<<" is "<<dist[N];
}

The code works fine and prints the minimum cost but I am not understanding the struct comp(); and how this works.

Shubhankar Bhadra
  • 11
  • 2
  • I might have misunderstood you, but comp is a callable object, you can refer to https://en.wikipedia.org/wiki/Function_object#In_C_and_C.2B.2B . The article first shows you the idea of function pointer in C and then the idea of callable object in C++. See also https://stackoverflow.com/questions/19278424/what-is-a-callable-object-in-c – CuriouslyRecurringThoughts Jun 16 '19 at 15:59
  • Possible duplicate of [Priority Queue Comparison](https://stackoverflow.com/questions/20826078/priority-queue-comparison) – Vlad Jun 16 '19 at 18:53

0 Answers0