javascript - ES6 图中的最短路径

Question

这是我实现的一个图，以获得 A 和 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);

当我运行它时，它给出 1, 7 但这不是最短路径。我在这里做错了什么。

Answer 1

您的代码中有 2 个问题(破坏了距离表的构建):

1. 您缺少索引:if (distanceTable[item.data] === -1) { -> 距离表中的每个项目都是数组，因此它需要是: if (distanceTable[item.data][0] === -1) {

2. 在 node js 中设置大小，使用 size 而不是 length ( as in documentation ) 因此 item.adjacencySet .length 总是 undefined 所以你需要改变: if (item.adjacencySet.length> 0) { 到 if (item.adjacencySet.大小 > 0) {

在这 2 次更改之后，您的代码返回路径 1 -> 0 -> 7

只是一个小问题:在抛出 TypeError 之前，您遗漏了一些 ; 和“new”...