OR-Tools  8.2
shortestpaths.h
Go to the documentation of this file.
1// Copyright 2010-2018 Google LLC
2// Licensed under the Apache License, Version 2.0 (the "License");
3// you may not use this file except in compliance with the License.
4// You may obtain a copy of the License at
5//
6// http://www.apache.org/licenses/LICENSE-2.0
7//
8// Unless required by applicable law or agreed to in writing, software
9// distributed under the License is distributed on an "AS IS" BASIS,
10// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11// See the License for the specific language governing permissions and
12// limitations under the License.
13
14// This file contains various shortest paths utilities.
15//
16// Keywords: directed graph, cheapest path, shortest path, Dijkstra, spp.
17
18#ifndef OR_TOOLS_GRAPH_SHORTESTPATHS_H_
19#define OR_TOOLS_GRAPH_SHORTESTPATHS_H_
20
21#include <functional>
22#include <memory>
23#include <string>
24#include <vector>
25
27#include "ortools/base/macros.h"
28
29namespace operations_research {
30
31// Dijsktra Shortest path with callback based description of the
32// graph. The callback returns the distance between two nodes, a
33// distance of 'disconnected_distance' indicates no arcs between these
34// two nodes. Ownership of the callback is taken by the function that
35// will delete it in the end. This function returns true if
36// 'start_node' and 'end_node' are connected, false otherwise.
37bool DijkstraShortestPath(int node_count, int start_node, int end_node,
38 std::function<int64(int, int)> graph,
39 int64 disconnected_distance, std::vector<int>* nodes);
40
41// Stable version of the Dijsktra Shortest path with callback based description
42// of the graph. The callback returns the distance between two nodes, a
43// distance of 'disconnected_distance' indicates no arcs between these
44// two nodes. Ownership of the callback is taken by the function that
45// will delete it in the end. This function returns true if
46// 'start_node' and 'end_node' are connected, false otherwise.
47bool StableDijkstraShortestPath(int node_count, int start_node, int end_node,
48 std::function<int64(int, int)> graph,
49 int64 disconnected_distance,
50 std::vector<int>* nodes);
51
52// Bellman-Ford Shortest path with callback-based description of the
53// graph. The callback returns the distance between two nodes, a
54// distance of 'disconnected_distance' indicates no arcs between these
55// two nodes. Ownership of the callback is taken by the function that
56// will delete it in the end. This function returns true if
57// 'start_node' and 'end_node' are connected, false otherwise. If
58// true, it will fill the 'nodes' vector with the sequence of nodes on
59// the shortest path between 'start_node' and 'end_node'.
60bool BellmanFordShortestPath(int node_count, int start_node, int end_node,
61 std::function<int64(int, int)> graph,
62 int64 disconnected_distance,
63 std::vector<int>* nodes);
64
65// A* Shortest path with function based description of the
66// graph. The graph function returns the distance between two nodes, a
67// distance of 'disconnected_distance' indicates no arcs between these
68// two nodes. Additionally, the heuristic callback returns a
69// an approximate distance between the node and the target, which guides
70// the search. If the heuristic is admissible (ie. never overestimates cost),
71// the A* algorithm returns an optimal solution.
72// This function returns true if 'start_node' and 'end_node' are
73// connected, false otherwise.
74bool AStarShortestPath(int node_count, int start_node, int end_node,
75 std::function<int64(int, int)> graph,
76 std::function<int64(int)> heuristic,
77 int64 disconnected_distance, std::vector<int>* nodes);
78
79} // namespace operations_research
80
81#endif // OR_TOOLS_GRAPH_SHORTESTPATHS_H_
int64_t int64
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
bool StableDijkstraShortestPath(int node_count, int start_node, int end_node, std::function< int64(int, int)> graph, int64 disconnected_distance, std::vector< int > *nodes)
Definition: dijkstra.cc:156
bool BellmanFordShortestPath(int node_count, int start_node, int end_node, std::function< int64(int, int)> graph, int64 disconnected_distance, std::vector< int > *nodes)
bool AStarShortestPath(int node_count, int start_node, int end_node, std::function< int64(int, int)> graph, std::function< int64(int)> heuristic, int64 disconnected_distance, std::vector< int > *nodes)
Definition: astar.cc:170
bool DijkstraShortestPath(int node_count, int start_node, int end_node, std::function< int64(int, int)> graph, int64 disconnected_distance, std::vector< int > *nodes)
Definition: dijkstra.cc:147