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，但这不是最短的路径。我在这里做错了什么？

- Melissa Stewart

---

抛出未捕获的引用错误：Queue 未定义。 - CertainPerformance

不确定是否解决了所有问题，但您可能想要使用 of 而不是 in，即 for (const [key, value] of Object.entries(table))。这将至少修复 undefined 值的问题。 - Mark

同时，在您的代码中永远不会出现这种情况：distanceTable[item.data] === -1，因为您将类似于 [-1, -1] 的数组分配给了距离表。 - Mark

@CertainPerformance编辑了完整的问题并更新了不起作用的函数。 - Melissa Stewart

这个错误是在循环第一次运行时出现的还是在其他阶段出现的？能否请您在致命错误之前分享一下“curr”的内容？ - dWinder

Answer 1

您的代码中有两个问题（破坏了距离表的构建）：

1. 您在以下代码中缺少索引：if (distanceTable[item.data] === -1) {，因此距离表中的每个项目都是数组，因此需要更改为：if (distanceTable[item.data][0] === -1) {

2. 使用node js检查大小时，请使用size而不是length（如文档所述），因此item.adjacencySet.length始终为undefined，因此您需要将if (item.adjacencySet.length> 0) {更改为if (item.adjacencySet.size > 0) {

进行这两个更改后，您的代码将返回路径1 -> 0 -> 7

只是一个小问题：在抛出 TypeError 之前，你缺少一些 ; 和 "new"...

- dWinder