Out of Memory error when implementing breadth first search algorithm

I got the following error:

[error][1] (E/DartVM  (14988): Exhausted heap space, trying to allocate 536870928 bytes.
E/flutter (14988): [ERROR:flutter/lib/ui/ui_dart_state.cc(148)] Unhandled Exception: Out of Memory)

When trying to implement a breadth_first search algorithm to find the shortest path in a graph. I found the algorithm written in C# and I am trying to rewrite it in dart/flutter.

The original code in C# can be found here.

My dart code:

import 'dart:collection';
import 'package:stack/stack.dart';
class Node<T>{
  int id;
  Node(this.id);
  String toString() => '$id';
}
class Graph<T>{
  final Map<Node, List<Node>> adj;
  Graph(this.adj);
  void AddEdge(Node node1,Node node2){
    if(!adj.containsKey(node1))
      adj[node1]=List<Node>();
    if(!adj.containsKey(node2))
      adj[node2]=List<Node>();
    adj[node1].add(node2);
    adj[node2].add(node1);
  }
  Stack<Node> ShortestPath(Node source, Node dest){
    var path=Map<Node<T>,Node<T>>();
    var distance=Map<Node<T>,int>();
    //adj.keys.forEach(( node) => distance[node]=-1);
    for(var node in adj.keys){
      distance[node]=-1;
    }
    distance[source]=0;
    var q=Queue<Node<T>>();
    q.add(source);
    while(q.isNotEmpty){
      var node=q.removeFirst();
      for(var adjs in adj[node].where((n) => distance[n]==-1)){
        distance[adjs]=distance[node]+1;
        path[adjs]=node;
        q.add(adjs);
      }
    }
    var res=Stack<Node>();
    var cur=dest;
    while(cur != res){
      res.push(cur);
      cur=path[cur];
    }
    res.push(source);
    return res;
  }
}
void main() {
  var g = new Graph({});
  var n1 = new Node<int>(1);
  var n2 = new Node<int>(2);
  var n3 = new Node<int>(3);
  var n4 = new Node<int>(4);
  var n5 = new Node<int>(5);
  var n6 = new Node<int>(6);
  var n7 = new Node<int>(7);
  g.AddEdge(n1, n2);
  g.AddEdge(n1, n3);
  g.AddEdge(n1, n4);
  g.AddEdge(n4, n5);
  g.AddEdge(n2, n6);
  g.AddEdge(n4, n7);
  g.AddEdge(n5, n6);
  g.AddEdge(n6, n7);
  var answ=g.ShortestPath(n1, n7);
  print(answ);
}

So what is the wrong with my program, and if anyone know better way to find shortest path in graph to use it in dart it will be great.

Thanks in advance

First, you main problem is properly that your while loop is not correct according to the C# implementation:

    var res=Stack<Node>();
var cur=dest;
while(cur != res){
res.push(cur);
cur=path[cur];
}
res.push(source);
return res;

This loop will never finish res and cur are entirely different types where cur are a Node and res are a Stack. If you check the C# implementation you can see this is not correct:

		var res = new Stack<Node<T>>();
		var cur = dest;
		while(cur != source) {
			res.Push(cur);
			cur = path[cur];
		}
		res.Push(source);
		return res;

So I think by comparing against source it will properly solve the problem. But there are a lot of smaller problems in you code where types are not really great and where you could make it a lot more type safe by using generics more places.

I have therefore added more typing information to you code (which I needed to do to catch the type error). I have also dropped the usage of the Stack class since I don't think it makes much sense. Also, the Stack class you got had no toString implementation so I just thought it was easier to just use a List and return that as the result:

import 'dart:collection';

class Node<T> {
  int id;
  Node(this.id);

  @override
  String toString() => '$id';
}

class Graph<T> {
  final Map<Node<T>, List<Node<T>>> adj;
  Graph(this.adj);
  void AddEdge(Node<T> node1, Node<T> node2) {
    if (!adj.containsKey(node1)) adj[node1] = <Node<T>>[];
    if (!adj.containsKey(node2)) adj[node2] = <Node<T>>[];
    adj[node1].add(node2);
    adj[node2].add(node1);
  }

  List<Node<T>> ShortestPath(Node<T> source, Node<T> dest) {
    final path = <Node<T>, Node<T>>{};
    final distance = <Node<T>, int>{};
    //adj.keys.forEach(( node) => distance[node]=-1);
    for (final node in adj.keys) {
      distance[node] = -1;
    }
    distance[source] = 0;
    final q = Queue<Node<T>>();
    q.add(source);
    while (q.isNotEmpty) {
      final node = q.removeFirst();
      for (final adjs in adj[node].where((n) => distance[n] == -1)) {
        distance[adjs] = distance[node] + 1;
        path[adjs] = node;
        q.add(adjs);
      }
    }
    final res = <Node<T>>[];
    var cur = dest;
    while (cur != source) {
      res.add(cur);
      cur = path[cur];
    }
    res.add(source);
    return res;
  }
}

void main() {
  final g = Graph<int>({});
  final n1 = Node<int>(1);
  final n2 = Node<int>(2);
  final n3 = Node<int>(3);
  final n4 = Node<int>(4);
  final n5 = Node<int>(5);
  final n6 = Node<int>(6);
  final n7 = Node<int>(7);
  g.AddEdge(n1, n2);
  g.AddEdge(n1, n3);
  g.AddEdge(n1, n4);
  g.AddEdge(n4, n5);
  g.AddEdge(n2, n6);
  g.AddEdge(n4, n7);
  g.AddEdge(n5, n6);
  g.AddEdge(n6, n7);
  final answ = g.ShortestPath(n1, n7);
  print(answ); // [7, 4, 1]
}