dijkstra.cpp

#include <cstdio>

#include <unordered_map>
#include <vector>

template <typename T>
struct Edge;

template <typename T>
struct Node;

template <typename T>
struct Node {
    T value;
    std::vector<Edge<T>> connections;
};

template <typename T>
struct Edge {
    unsigned int weight;
    Node<T>& neighbour;
};

template <typename T>
const Node<T>* findMinimumDistanceNode(const std::unordered_map<T, unsigned int>& distances,
                              const std::unordered_map<T, const Node<T>*> nodeSet)
{
    auto minimumNode = nodeSet.begin()->second;
    auto maxDistance = (unsigned int)(-1);

    for (const auto& keyPair : nodeSet) {
        const auto node = keyPair.second;

        auto distance = distances.at(node->value);
        if (distance < maxDistance) {
            maxDistance = distance;
            minimumNode = node;
        }
    }
    return minimumNode;
}

template <typename T>
std::pair<unsigned int, std::unordered_map<T, unsigned int>> dijsktraMinimumPath(const std::vector<Node<T>>& nodes,
                                 T start,
                                 T end)
{
    std::unordered_map<T, const Node<T>* > nodeSet;
    std::unordered_map<T, unsigned int> distances;

    // nodeSet.reserve(nodes.size());
    distances.reserve(nodes.size());

    for (const auto& node : nodes) {
        nodeSet[node.value] = &node;
        distances[node.value] = (unsigned int)(-1);
    }

    if (nodeSet.find(start) == nodeSet.end()) {
        return {-1, {}};
    }

    if (nodeSet.find(end) == nodeSet.end()) {
        return {-1, {}};
    }

    distances[start] = 0;

    while (!nodeSet.empty()) {
        auto& minimumNode = *findMinimumDistanceNode(distances, nodeSet);

        nodeSet.erase(minimumNode.value);

        for (const auto& edge : minimumNode.connections) {
            auto alternativeDistance = distances[minimumNode.value] + edge.weight;
            auto neighbouringDistance = distances[edge.neighbour.value];

            if (alternativeDistance < neighbouringDistance) { 
                distances[edge.neighbour.value] = alternativeDistance;
            }
        }
    }
    return {distances[end], distances};
}

int main()
{
    auto nodes = std::vector<Node<unsigned int>>({
        {0, {}},
        {1, {}},
        {2, {}},
        {3, {}},
        {4, {}},
        {5, {}},
    });

    nodes[0].connections.push_back({7, nodes[1]});
    nodes[0].connections.push_back({9, nodes[2]});
    nodes[0].connections.push_back({14, nodes[5]});
    
    nodes[1].connections.push_back({7, nodes[0]});
    nodes[1].connections.push_back({10, nodes[2]});
    nodes[1].connections.push_back({15, nodes[3]});
    
    nodes[2].connections.push_back({9, nodes[0]});
    nodes[2].connections.push_back({10, nodes[1]});
    nodes[2].connections.push_back({11, nodes[3]});
    nodes[2].connections.push_back({2, nodes[5]});
    
    nodes[3].connections.push_back({15, nodes[1]});
    nodes[3].connections.push_back({11, nodes[2]});
    nodes[3].connections.push_back({6, nodes[4]});
    
    nodes[4].connections.push_back({6, nodes[3]});
    nodes[4].connections.push_back({9, nodes[5]});
    
    nodes[5].connections.push_back({14, nodes[0]});
    nodes[5].connections.push_back({2, nodes[2]});
    nodes[5].connections.push_back({9, nodes[4]});

    printf("%d\n", dijsktraMinimumPath<unsigned int>(nodes, 0, 4).first);    
}