Shortest path in a graph in ES6

Question

This is my implementation of a graph, to get the shortest path between A and B.

class Queue {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;

  }
  offer(item) {
    const p = new QueueNode(item);
    this.size++;
    if (this.head === null) {
      this.head = p;
      this.tail = p;
      return;
    }
    this.tail.next = p;
    this.tail = p;

  }
  poll() {
    if (this.size === 0) {
      throw TypeError("Can't deque off an empty queue.");
    }
    this.size--;
    const item = this.head;
    this.head = this.head.next;
    return item.val;

  }
  peek() {
    if (this.size === 0) {
      throw TypeError("Empty Queue.")
    }
    return this.head.val;
  }
  isEmpty() {
    return this.head === null;

  }

}
class QueueNode {
  constructor(item) {
    this.val = item;
    this.next = null;
  }


}
class Graph {

  constructor(directed = false) {
    this.numVertices = 0;
    this.directed = directed;
    this.dict = {}
  }
  addEdge(v1, v2, weight = 1) {
    let p, q;
    if (v1 in this.dict) {
      p = this.dict[v1];
    } else {
      p = new GraphNode(v1);
      this.dict[v1] = p;
      this.numVertices++;
    }
    if (v2 in this.dict) {
      q = this.dict[v2];
    } else {
      q = new GraphNode(v2);
      this.dict[v2] = q;
      this.numVertices++;
    }
    p.addEdge(q);
    if (!this.directed) {
      q.addEdge(p);
    }

  }

  stringify() {
    for (const [key, value] of Object.entries(this.dict)) {
      console.log(`${key}: ${[...value.adjacencySet].map(x => x.data)}`);
    }

  }



  buildDistanceTable(source) {
    let p;
    if (this.dict[source] === undefined) {
      throw TypeError('Vertex not present in graph')
    } else {
      p = this.dict[source];
    }
    const distanceTable = {};
    for (const [key, value] of Object.entries(this.dict)) {
      distanceTable[key] = [-1, -1];
    }
    distanceTable[p.data] = [0, p.data];

    const queue = new Queue();
    queue.offer(p);

    while (!queue.isEmpty()) {
      let curr = queue.poll();

      let curr_distance = distanceTable[curr.data][0];

      curr.adjacencySet.forEach((item) => {

        if (distanceTable[item.data] === -1) {
          distanceTable[item.data] = [1 + curr_distance, curr.data];
          console.log(distanceTable);
          if (item.adjacencySet.length > 0) {
            queue.offer(item);
          }
        }
      })

    }
    return distanceTable;
  }

  shortestPath(source, destination) {
    const distanceTable = this.buildDistanceTable(source);
    const path = [destination];
    let prev = distanceTable[destination][1];
    while (prev !== -1 && prev !== source) {
      path.unshift(prev);
      prev = distanceTable[prev][1];
    }
    if (prev === null) {
      console.log("There's no path from source to destination");
    } else {
      path.unshift(source);
      path.map(item => {
        console.log(item);
      });
    }
  }
}

class GraphNode {
  constructor(data) {
    this.data = data;
    this.adjacencySet = new Set();
  }
  addEdge(node) {
    this.adjacencySet.add(node)
  }
}

graph = new Graph(directed = false);
graph.addEdge(0, 1);
graph.addEdge(1, 2);
graph.addEdge(1, 3);
graph.addEdge(2, 3);
graph.addEdge(1, 4);
graph.addEdge(3, 5);
graph.addEdge(5, 4);
graph.addEdge(3, 6);
graph.addEdge(6, 7);
graph.addEdge(0, 7);

graph.stringify();
graph.shortestPath(1, 7);

When I run this it give 1, 7 however that's not the shortest path. What am I doing wrong here.

Answer 1

You have 2 issue in your code (that sabotage the building of the distance table):

1. You missing index in: if (distanceTable[item.data] === -1) { -> each item in the distance table is of array therefor it need to be: if (distanceTable[item.data][0] === -1) {

2. Set size in node js checked with size and not length (as in documentation) therefor item.adjacencySet.length is always undefined so you need to change: if (item.adjacencySet.length> 0) { to if (item.adjacencySet.size > 0) {

After those 2 changes your code return me path of 1 -> 0 -> 7

Just small side issue: you missing some ; and "new" before throwing TypeError...