dijkstra

#include<iostream>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<climits>
#include<functional>

// Node and Edge Structures
class Node {
    private:
    Node *predecessor;

    public:
    const char value;
    int hops;

    Node(char c)
    : value(std::toupper(c)), hops(INT_MAX), predecessor(nullptr) {}

    void setPredecessor(Node& n) {
        predecessor = &n;
    }

    const Node * getPredecessor() {
        if(predecessor != nullptr)
            return predecessor;
        return nullptr;
    }
};

class Edge {
    public:
    Node& from;
    Node& to;
    const int weight;
};

// Create a graph
Node source('S');                   // Create a source node

std::map<char, Node&> all_nodes = {
    {'T', *(new Node('T'))},
    {'Y', *(new Node('Y'))},
    {'Z', *(new Node('Z'))},
    {'X', *(new Node('X'))},
};

std::vector<Edge> all_edges = {
    {.from = source, .to = all_nodes.at('T'), .weight = 10},
    {.from = source, .to = all_nodes.at('Y'), .weight = 5},
    {.from = all_nodes.at('T'), .to = all_nodes.at('Y'), .weight = 2},
    {.from = all_nodes.at('Y'), .to = all_nodes.at('T'), .weight = 3},
    {.from = all_nodes.at('T'), .to = all_nodes.at('X'), .weight = 1},
    {.from = all_nodes.at('Y'), .to = all_nodes.at('X'), .weight = 9},
    {.from = all_nodes.at('Z'), .to = all_nodes.at('X'), .weight = 6},
    {.from = all_nodes.at('X'), .to = all_nodes.at('Z'), .weight = 4},
    {.from = all_nodes.at('Y'), .to = all_nodes.at('Z'), .weight = 2},
    {.from = all_nodes.at('Z'), .to = source, .weight = 7},
};


// Supporting class and functions
class queue_cmp {
    public:
    bool operator()(const Node& a, const Node& b) {
        return a.hops>b.hops;
    }
};

class set_cmp {
    public:
    bool operator()(const Node& a, const Node& b) {
        return a.hops != b.hops;
    }
};

// Find adjacent Edges
std::vector<std::reference_wrapper<Edge>> r_vector;
std::vector<std::reference_wrapper<Edge>>& adjacentEdges(const Node& n) {
    std::cout<<n.value<<":"<<std::endl;
    r_vector.clear();
    for(auto& e: all_edges) {
        if(e.from.value == n.value) {
            r_vector.push_back(e);
            std::cout<<e.from.value<<" -> "<<e.to.value<<"\t"<<e.weight<<std::endl;
        }
    }

    std::cout<<std::endl;

    return r_vector;
}



int main() {
    // Initialize source node
    source.hops = 0;

    std::set<std::reference_wrapper<Node>, set_cmp> dijkstra_Set;
    std::priority_queue<Node, std::vector<std::reference_wrapper<Node>>, queue_cmp> dijkstra_Queue;
    dijkstra_Queue.push(source);
    for(auto& v: all_nodes) {
        dijkstra_Queue.push(v.second);
    }


    while(!dijkstra_Queue.empty()) {
        Node& u = dijkstra_Queue.top().get();
        dijkstra_Queue.pop();
        dijkstra_Set.emplace(u);

        // std::cout<<u.value<<": ";
        for(Edge& e: adjacentEdges(u)) {
            // std::cout<<e.to.value<<" ";
            // Relax(u, v, w)
            if(e.to.hops > u.hops + e.weight) {
                e.to.hops = u.hops + e.weight;
                e.to.setPredecessor(u);

                // std::cout<<u.value<<" -> "<<e.to.value<<std::endl;
            }
        }
        // std::cout<<std::endl;
    }

    for(auto& v: all_nodes) {
        if(v.second.getPredecessor() != nullptr)
        std::cout<<v.second.getPredecessor()->value<<" -> "<<v.second.value<<std::endl;
    }

}