Graph/dijkstra library
🚦 Dijkstra's Algorithm (Single-Source Shortest Paths)
Computes shortest path distances from start to all nodes in a graph with
non-negative edge weights. Graph is represented as an adjacency list of
WeightedEdges.
- Time complexity (simple implementation): O(V^2 + E)
- Space complexity: O(V)
- Throws ArgumentError if a negative edge weight is encountered.
Example:
final graph = <String, List<WeightedEdge<String>>>{
'A': [WeightedEdge('A', 'B', 1), WeightedEdge('A', 'C', 4)],
'B': [WeightedEdge('B', 'C', 2), WeightedEdge('B', 'D', 5)],
'C': [WeightedEdge('C', 'D', 1)],
'D': [],
};
final dist = dijkstra(graph, 'A');
// dist: {'A':0, 'B':1, 'C':3, 'D':4}