我的 Dijkstra 算法实现没有 return 最短路径

Question

我尝试在 JavaScript 中实现 Dijkstra 的最短路径算法，并用多个示例对其进行了测试。

我正在使用此图查看它的行为方式：

如果我想找到从 A 到 I 的最短路径，结果应该是 [A, D, C, F, G, H, I]，距离等于 10。

但我的实现 returns 路径为 [A、B、E、J、F、G、H、I]，距离为 14。

这是我的 JavaScript 代码：

const graph = {
    A: {B: 3, C: 4, D: 2},
    B: {A: 3, D: 6, E: 1},
    C: {A: 4, D: 1, F: 3},
    D: {A: 2, B: 6, C: 1, E: 5},
    E: {B: 1, D: 5, J: 1},
    F: {C: 3, G: 2, J: 5},
    G: {F: 2, H: 1, I: 3},
    H: {G: 1, I: 1, X: 2},
    I: {G: 3, H: 1, X: 8},
    J: {E: 1, F: 5, X: 6},
    X: {H: 2, I: 8, J: 6},
};

// The class Dsp:

class Dsp {
  constructor() {
    //Previous node after update of distance
    this.prev = {};
    //Distances of each node
    this.distances = {};
    //Array of unvisited neighbors
    this.unvisitedn = [];
    //Path of visited nodes from first to final node
    this.path = [];
  }

  findsp(graph, start, end) {

    //Register graph data 
    this.registerGraphData(graph, start);

    //Set the starting node as the current node
    let cn = start;

    //While there are unvisited nodes
    while (this.unvisitedn.length > 0) {
      //Mark the currentNode as visited
      this.markAsVisited(cn);

      //Compare distance from current node to unvisited neighbors
      let nodes = this.compareNodeDistances(graph, cn);

      //Update neighbor distance
      this.updateNodeDistances(nodes, cn);

      //Compare each unvisited neighbor and choose the one with the lowest distances
      //Set the choosed node as the new current node
      cn = this.selectNextNode(graph, cn);
    }

    return this.generatePath(start, end);
  }

  registerGraphData(graph, start) {

    //Set starting weight for all nodes
    const higherWeight = 10000;

    //For each node in the graph
    for (let node in graph) {
      //If the node is the starting node 
      if (node == start)
        //Set starting weight as 0
        this.distances[node] = 0;
      //else set the higherWeight
      else
        this.distances[node] = higherWeight;

      //Add to the unvisited nodes
      this.unvisitedn.push(node);
    }

    console.log(this.distances);
    console.log(this.unvisitedn);
  }

  markAsVisited(cn) {

    console.log('Visiting', cn);

    let index = this.unvisitedn.indexOf(cn);
    this.unvisitedn.splice(index, 1);
  }

  getUnvisitedNeighbors(graph, cn) {

    //All current node neighbors
    let nbs = graph[cn];
    let unbs = [];

    for (let nb in nbs) {
      if (this.unvisitedn.includes(nb))
        unbs.push(nb);
    }

    console.log(cn, 'Unvisited neighbors:', unbs);

    return unbs;
  }

  compareNodeDistances(graph, cn) {

    let unbs = this.getUnvisitedNeighbors(graph, cn);

    //new distances
    let newDistances = {};

    //For all currentNode neighbors
    for (let nb of unbs) { //Substituted unbs

      //Neighbor Weight
      let nbw = graph[cn][nb];
      //console.log('Neighbor weight', nbw);

      //neighbor distance
      let nbd = this.distances[nb];
      //console.log('Neighbor distance', nbd);

      //current node distance
      let cnd = this.distances[cn];
      //console.log('Current node distance', cnd);

      //If the neighbor distance > current node distance + neighbor weight
      if (nbd > cnd + nbw)
        newDistances[nb] = cnd + nbw;
    }

    console.log('new distances:', newDistances);

    return newDistances;
  }

  updateNodeDistances(nodes, cn) {

    //Update distances for each neighbor that was compared
    for (let node in nodes) {
      console.log(nodes);


      this.distances[node] = nodes[node];
      this.prev[node] = cn;
    }

    console.log("Node distances after update", this.distances);
    console.log("Node previous nodes after update", this.prev);
  }

  selectNextNode(graph, cn) {
    let unbs = this.getUnvisitedNeighbors(graph, cn);
    let mind = 100000;
    let nextn = null;

    //If there are unvisited neighbors
    if (unbs.length > 0) {
      for (let nb of unbs) {
        if (this.distances[nb] < mind) {
          mind = this.distances[nb];
          nextn = nb;
        }
      }
    } else {
      nextn = this.unvisitedn[0];
    }

    return nextn;
  }

  generatePath(start, end) {

    let cn = end;
    let path = {};
    let nodes = [];

    while (cn !== start) {
      nodes.push(cn);
      cn = this.prev[cn];
    }

    nodes.push(start);
    nodes.reverse();

    path['nodes'] = nodes;
    path['distance'] = this.distances[end];

    return path;
  }
}

let shp = new Dsp();

console.log(shp.findsp(graph, 'A', 'I'));

我想了解我编写的步骤有什么问题。

我做错了什么？是否有一些额外的步骤或考虑？

Answer 1

问题是您没有执行最佳优先搜索。您的代码确实执行了深度优先搜索，您只需优化将从 current 节点中选择的未访问的 neighbor。但是你应该从 all 个未访问的节点中取最小距离的节点，而不仅仅是 current 节点的邻居。

另请参阅 Wikipedia 上算法说明的第 6 步：

Otherwise, select the unvisited node that is marked with the smallest tentative distance, set it as the new "current node"

所以问题出在selectNextNode。可以更正为：

selectNextNode(graph, cn) {
    let mindist = Infinity;
    let best;
    for (let node of this.unvisitedn) {
        if (this.distances[node] < mindist) {
            mindist = this.distances[node];
            best = node;
        }
    }
    return best;
}

然而，这是一个天真的实现，因为在每一轮中你都必须再次找到最小值：这使得算法不是最优的。一个真正的 Dijkstra 算法会使用一个优先级队列，例如堆，这使得这个查找更有效率。

用堆实现

不幸的是 JavaScript 没有（还）提供原生堆实现，所以我们不得不抛出我们自己的或者引用一个库。我从我对的回答中获取了实现。有关该实施的更多详细信息，请参阅此处。

我认为最短路径算法的实现不保证使用class。像你的 findsp 这样的功能应该足够了。

这里是：

/* MinHeap minimised - taken from  */
const MinHeap={siftDown(h,i=0,v=h[i]){if(i<h.length){let k=v[0];while(1){let j=i*2+1;if(j+1<h.length&&h[j][0]>h[j+1][0])j++;if(j>=h.length||k<=h[j][0])break;h[i]=h[j];i=j;}h[i]=v}},heapify(h){for(let i=h.length>>1;i--;)this.siftDown(h,i);return h},pop(h){return this.exchange(h,h.pop())},exchange(h,v){if(!h.length)return v;let w=h[0];this.siftDown(h,0,v);return w},push(h,v){let k=v[0],i=h.length,j;while((j=(i-1)>>1)>=0&&k<h[j][0]){h[i]=h[j];i=j}h[i]=v;return h}};

function DijkstraShortestPath(graph, start, end) {
    // Heap with one entry: distance is 0 at start, and there is no previous.
    let heap = [[0, start, null]]; 
    let prev = {};
    
    while (heap.length) {
        let [distance, current, cameFrom] = MinHeap.pop(heap);
        if (current in prev) continue; // Already visited
        prev[current] = cameFrom; // Mark as visited
        if (current == end) { // Found!
            // Reconstruct path
            let path = [];
            while (current) {
                path.push(current);
                current = prev[current];
            }
            path.reverse();
            return { path, distance };
        }
        // Push unvisited neighbors on the heap
        for (let [neighbor, edge] of Object.entries(graph[current])) {
            if (!(neighbor in prev)) MinHeap.push(heap, [distance + edge, neighbor, current]);
        }
    }
}

// Demo:
const graph = {
    A: {B: 3, C: 4, D: 2},
    B: {A: 3, D: 6, E: 1},
    C: {A: 4, D: 1, F: 3},
    D: {A: 2, B: 6, C: 1, E: 5},
    E: {B: 1, D: 5, J: 1},
    F: {C: 3, G: 2, J: 5},
    G: {F: 2, H: 1, I: 3},
    H: {G: 1, I: 1, X: 2},
    I: {G: 3, H: 1, X: 8},
    J: {E: 1, F: 5, X: 6},
    X: {H: 2, I: 8, J: 6},
}

console.log(DijkstraShortestPath(graph, 'A', 'I'));

我的 Dijkstra 算法实现没有 return 最短路径

My Dijkstra's algorithm implementation does not return shortest path

javascript

graph-algorithm

shortest-path

用堆实现