bellman_ford.h

#ifndef CPP_ALGORITHM_BELLMAN_FORD_H
#define CPP_ALGORITHM_BELLMAN_FORD_H

#include <map>
#include <set>
#include <stdexcept>
#include <vector>

namespace BellmanFord
{
    struct Vertex
    {
        explicit Vertex(const char id)
            : id(id), neighbors(std::set<Vertex*>()), predecessor(nullptr), distance(std::numeric_limits<int>::max())
        {
        }

        char id;
        std::set<Vertex*> neighbors;
        Vertex* predecessor;
        int distance;
    };

    class Graph
    {
    public:
        void AddVertex(Vertex& v);
        void AddEdge(Vertex& u, Vertex& v, int weight);

        /**
         * \brief Bellman-Ford algorithm. Find the shortest path from a source vertex to all other vertices.
         * \details A single source shortest path algorithm that can handle negative edge weights.
         * It finds the shortest path from a source vertex to all other vertices in a weighted graph.
         * \param source source vertex
         */
        void BellmanFordAlgorithm(Vertex& source);

        std::vector<Vertex*> vertices;
        std::vector<std::tuple<Vertex*, Vertex*>> adjacency_list;
        std::map<std::pair<char, char>, int> weight_list;
    };
}

// ----------------------------------------------------------------------------
inline void BellmanFord::Graph::BellmanFordAlgorithm(Vertex& source)
{
    for (int i = 0; i < static_cast<int>(vertices.size()) - 1; ++i)
    {
        for (auto& [u, v] : adjacency_list)
        {
            // Relaxation
            const auto weight_uv = weight_list.at(std::make_pair(u->id, v->id));
            if (v->distance > (u->distance + weight_uv))
            {
                v->distance = u->distance + weight_uv;
                v->predecessor = u;
            }
        }
    }
    for (auto& [u, v] : adjacency_list)
    {
        if (v->distance > (u->distance + weight_list.at(std::make_pair(u->id, v->id))))
        {
            throw std::runtime_error("Graph has a negative cycle");
        }
    }
}

// ----------------------------------------------------------------------------
inline void BellmanFord::Graph::AddVertex(Vertex& v)
{
    vertices.push_back(&v);
}

// ----------------------------------------------------------------------------
inline void BellmanFord::Graph::AddEdge(Vertex& u, Vertex& v, int weight)
{
    adjacency_list.emplace_back(&u, &v);
    u.neighbors.insert(&v);
    weight_list.insert(std::make_pair(std::make_pair(u.id, v.id), weight));
}

#endif