Graph/shortest_path library

🛤️ Shortest Path (Unweighted) via BFS

Computes a shortest path between start and target in an unweighted graph using BFS, returning the path as a list from start to target. Returns an empty list if no path exists.

  • Time complexity: O(V + E)
  • Space complexity: O(V)

Example:

final graph = {
  'A': ['B', 'C'], 'B': ['D', 'E'], 'C': ['F'], 'E': ['F']
};
final path = shortestPathUnweighted(graph, 'A', 'F');
// path: ['A', 'C', 'F']

Functions

shortestPathUnweighted<T>(Map<T, List<T>> graph, T start, T target) → List<T>