operations_research::ArcWithLength Struct Reference

Detailed Description

Todo

(b/332475231): extend to non-floating lengths.

(b/332476147): extend to allow for length functor.

This library provides a few APIs to compute the shortest path on a given directed acyclic graph (DAG).

In the DAG, multiple arcs between the same pair of nodes is allowed. However, self-loop arcs are not allowed.

Note

we use the length formalism here, but the arc lengths can represent any numeric physical quantity. A shortest path will just be a path minimizing this quantity where the length of a path is the sum of the length of its arcs. An arc length can be negative, or +inf (indicating that it should not be used). An arc length cannot be -inf or nan. Basic API. from and to should both be in [0, num_nodes). If the length is +inf, then the arc should not be used.

Definition at line 54 of file dag_shortest_path.h.

#include <dag_shortest_path.h>

Public Attributes
int	from = 0
int	to = 0
double	length = 0.0

Member Data Documentation

from

int operations_research::ArcWithLength::from = 0

Definition at line 55 of file dag_shortest_path.h.

length

double operations_research::ArcWithLength::length = 0.0

Definition at line 57 of file dag_shortest_path.h.

to

int operations_research::ArcWithLength::to = 0

Definition at line 56 of file dag_shortest_path.h.

---

The documentation for this struct was generated from the following file:

• ortools/graph/dag_shortest_path.h