Program Listing for File FloydWarshall.hpp¶

/*  FloydWarshall.hpp
 *
 *  Created on: 15.02.2025
 *  Authors: Andreas Scharf (andreas.b.scharf@gmail.com)
 *
 */

#ifndef NETWORKIT_DISTANCE_FLOYD_WARSHALL_HPP_
#define NETWORKIT_DISTANCE_FLOYD_WARSHALL_HPP_

#include <networkit/base/Algorithm.hpp>
#include <networkit/graph/Graph.hpp>

namespace NetworKit {

class FloydWarshall : public Algorithm {
public:
    FloydWarshall(const Graph &G);
    void run() override;

    edgeweight getDistance(node source, node target) const;
    bool isNodeInNegativeCycle(node u) const;

    std::vector<node> getNodesOnShortestPath(node source, node target) const;

private:
    const Graph *graph;
    static constexpr edgeweight infiniteDistance = std::numeric_limits<edgeweight>::max();
    std::vector<std::vector<edgeweight>> distances;
    std::vector<bool> nodesInNegativeCycle;
    std::vector<std::vector<node>> pathMatrix;
    std::vector<std::vector<count>> hops;
    void tagNegativeCycles();
};
} // namespace NetworKit

#endif // NETWORKIT_DISTANCE_FLOYD_WARSHALL_HPP_