shortestpaths.h

// Copyright 2010-2021 Google LLC
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

// This file contains various shortest paths utilities.
//
// Keywords: directed graph, cheapest path, shortest path, Dijkstra, spp.

#ifndef OR_TOOLS_GRAPH_SHORTESTPATHS_H_
#define OR_TOOLS_GRAPH_SHORTESTPATHS_H_

#include <cstdint>
#include <functional>
#include <memory>
#include <string>
#include <vector>

#include "ortools/base/integral_types.h"
#include "ortools/base/macros.h"

namespace operations_research {

// Dijsktra Shortest path with callback based description of the
// graph.  The callback returns the distance between two nodes, a
// distance of 'disconnected_distance' indicates no arcs between these
// two nodes. Ownership of the callback is taken by the function that
// will delete it in the end.  This function returns true if
// 'start_node' and 'end_node' are connected, false otherwise.
bool DijkstraShortestPath(int node_count, int start_node, int end_node,
                          std::function<int64_t(int, int)> graph,
                          int64_t disconnected_distance,
                          std::vector<int>* nodes);

// Stable version of the Dijsktra Shortest path with callback based description
// of the graph.  The callback returns the distance between two nodes, a
// distance of 'disconnected_distance' indicates no arcs between these
// two nodes. Ownership of the callback is taken by the function that
// will delete it in the end.  This function returns true if
// 'start_node' and 'end_node' are connected, false otherwise.
bool StableDijkstraShortestPath(int node_count, int start_node, int end_node,
                                std::function<int64_t(int, int)> graph,
                                int64_t disconnected_distance,
                                std::vector<int>* nodes);

// Bellman-Ford Shortest path with callback-based description of the
// graph.  The callback returns the distance between two nodes, a
// distance of 'disconnected_distance' indicates no arcs between these
// two nodes.  Ownership of the callback is taken by the function that
// will delete it in the end.  This function returns true if
// 'start_node' and 'end_node' are connected, false otherwise. If
// true, it will fill the 'nodes' vector with the sequence of nodes on
// the shortest path between 'start_node' and 'end_node'.
bool BellmanFordShortestPath(int node_count, int start_node, int end_node,
                             std::function<int64_t(int, int)> graph,
                             int64_t disconnected_distance,
                             std::vector<int>* nodes);

// A* Shortest path with function based description of the
// graph.  The graph function returns the distance between two nodes, a
// distance of 'disconnected_distance' indicates no arcs between these
// two nodes. Additionally, the heuristic callback returns a
// an approximate distance between the node and the target, which guides
// the search. If the heuristic is admissible (ie. never overestimates cost),
// the A* algorithm returns an optimal solution.
// This function returns true if 'start_node' and 'end_node' are
// connected, false otherwise.
bool AStarShortestPath(int node_count, int start_node, int end_node,
                       std::function<int64_t(int, int)> graph,
                       std::function<int64_t(int)> heuristic,
                       int64_t disconnected_distance, std::vector<int>* nodes);

}  // namespace operations_research

#endif  // OR_TOOLS_GRAPH_SHORTESTPATHS_H_