findBestPath<T extends E> method

(Path<T>, double) findBestPath<T extends E>(
  1. WeightedWalkable<T> graph,
  2. T start,
  3. Goal<T> goal, {
  4. Tracer<T>? tracer,
})

Returns an optimal path (and it's total cost) in graph from start to a node that satisfies goal.

If the initial node satisfies the goal, the path will contain only the start node, and the cost will be zero. If the path is not found, the total cost will be double.infinity.

If no path can be found, Path.notFound is returned.

A node will never be included in the path more than once, as determined by Object.== on the node, unless the source node is also a successor of itself, in which case it will be included twice (once at the beginning and once at the end), otherwise it will only be included at the start.

Impassable Nodes

There are two ways to represent impassable nodes in a graph:

  • Omit the node from the graph entirely, i.e. no edge leads to it;
  • Calculate the weight of the edge to the node as double.infinity.

Tracing

May provide a tracer to capture finer-detail events during the traversal.

If omitted, no tracing is performed.

Example

final graph = WeightedWalkable.from({
  'a': [('b', 1.0), ('c', 2.0)],
  'b': [('c', 3.0)],
  'c': [('d', 4.0)],
});

final (path, cost) = dijkstra.findBestPath(graph, 'a', Goal.node('d'));
print(path); // Path(['a', 'c', 'd'])
print(cost); // 6.0

Implementation

(Path<T> path, double cost) findBestPath<T extends E>(
  WeightedWalkable<T> graph,
  T start,
  Goal<T> goal, {
  Tracer<T>? tracer,
}) {
  if (goal.success(start)) {
    return (Path([start]), 0.0);
  }
  return findBestPathExclusive(graph, start, goal, tracer: tracer);
}