Consider adding a shortestPath helper

[kevmoo]

Here's a tested implementation.

The only downside: I use PriorityQueue from pkg:collection. You could nix that and loose a bit of perf – whatever... CC @natebosch

import 'dart:collection';

import 'package:collection/collection.dart' show PriorityQueue;

/// If [sourceNode] equals [targetNode], `true` is always returned.
///
/// Assumes that [T] implements correct and efficient `==` and `hashCode`.
List<T> shortestPath<T>(
        T sourceNode, T targetNode, Iterable<T> Function(T) edgeWeight) =>
    shortestWeightedPath(sourceNode, targetNode,
        (T node) => edgeWeight(node).map((n) => MapEntry(n, 1)))?.value;

/// The value returned from [edgeWeight] must be greater than zero. This
/// requirement is verified in an assert. If violated When running without
/// asserts, the behavior is undefined.
///
/// If [sourceNode] equals [targetNode], `true` is always returned.
///
/// Assumes that [T] implements correct and efficient `==` and `hashCode`.
MapEntry<num, List<T>> shortestWeightedPath<T>(T sourceNode, T targetNode,
    Iterable<MapEntry<T, num>> Function(T) edgeWeight) {
  if (sourceNode == targetNode) {
    return MapEntry<num, List<T>>(0, []);
  }

  final distances = HashMap<T, MapEntry<num, List<T>>>();
  distances[sourceNode] = MapEntry<num, List<T>>(0, []);

  int compareDistance(T a, T b) {
    final distanceA = distances[a]?.key ?? double.infinity;
    final distanceB = distances[b]?.key ?? double.infinity;
    return distanceA.compareTo(distanceB);
  }

  final toVisit = PriorityQueue<T>(compareDistance)..add(sourceNode);

  MapEntry<num, List<T>> bestOption;

  while (toVisit.isNotEmpty) {
    final current = toVisit.removeFirst();
    final distanceToCurrent = distances[current];

    if (bestOption != null && distanceToCurrent.key >= bestOption.key) {
      // Skip any existing `toVisit` items that have no change of being
      // better than bestOption (if it exists)
      continue;
    }

    for (var edge in edgeWeight(current)) {
      assert(edge.value > 0, 'Edge weight must be greater than zero.');
      final existingDistance = distances[edge.key];

      final newOptionDistance = distanceToCurrent.key + edge.value;

      if (existingDistance == null ||
          existingDistance.key > newOptionDistance) {
        final newOption = MapEntry<num, List<T>>(newOptionDistance,
            distanceToCurrent.value.followedBy(<T>[edge.key]).toList());

        if (edge.key == targetNode) {
          assert(bestOption == null || bestOption.key > newOptionDistance);
          bestOption = newOption;
        }

        distances[edge.key] = newOption;
        if (bestOption == null || bestOption.key > newOption.key) {
          // Only add a node to visit if it might be a better path to the
          // target node
          toVisit.add(edge.key);
        }
      }
    }
  }

  assert(bestOption == distances[targetNode]);
  return bestOption;
}

[natebosch]

haven't looked closely at the code but I like the idea in general. I don't think there is an overly strong need to avoid a dependency on collection so I'm not super concerned about that.