Dijkstra的算法应该返回什么？

Question

我是一个前端Javascript开发人员，但我想学习一些图论来为谷歌面试做准备，我查阅了Dijkstra算法的一些实现。

这里列出的示例https://github.com/mburst/dijkstras-algorithm/blob/master/dijkstras.js似乎适合于找到两个节点之间的最短路径，并返回两个节点之间的最短节点路径，但维基百科上的伪代码版本似乎同时返回了"prev和dist“--它们应该是什么？

我尝试修改github示例以匹配维基百科伪代码，返回距离似乎给出了来自startVertex的每一个的最短的数字距离。但是prev没有返回最短路径。

var INFINITY = 1/0;

function PriorityQueue () {
  this._nodes = [];

  this.enqueue = function (priority, key) {
    this._nodes.push({key: key, priority: priority });
    this.sort();
  }
  this.dequeue = function () {
    return this._nodes.shift().key;
  }
  this.sort = function () {
    this._nodes.sort(function (a, b) {
      return a.priority - b.priority;
    });
  }
  this.isEmpty = function () {
    return !this._nodes.length;
  }
}


function Graph(){
  this.vertices = {};

  this.addVertex = function(name, edges){
    edges = edges || null;
    this.vertices[name] = edges;
  }
}


function djikstra(graph, startVertex) {
  var nodes = new PriorityQueue();

  var distances = {};
  var previous = {};

  for(vertex in graph.vertices) {
    if (vertex === startVertex) {
      distances[vertex] = 0;
      nodes.enqueue(0, vertex);
    } else {
      distances[vertex] = INFINITY;
      nodes.enqueue(INFINITY, vertex);
    }

    previous[vertex] = null;
  }


  while(!nodes.isEmpty()) {
    var smallest = nodes.dequeue();

    for(var neighbor in graph.vertices[smallest]) {
      var alt = distances[smallest] + graph.vertices[smallest][neighbor];

      if(alt < distances[neighbor]) {
        distances[neighbor] = alt;
        previous[neighbor] = smallest;
      }
    }
  }

  return distances;
}

var graph = new Graph();

graph.addVertex('S', {V: 1, W: 4});
graph.addVertex('V', {W: 2, T: 6});
graph.addVertex('W', {T: 3});
graph.addVertex('T');


console.log(djikstra(graph, 'S'));
//
{ S: 0, V: 1, W: 3, T: 6 }

Answer 1

Dijkstra算法是一种算法，它为一个非负图提供从某个点到所有其他点的最短距离。

有许多不同的修改。您可以返回两个节点之间的距离、节点与所有其他节点之间的距离、距离与路径、距离和前一个节点(这足以构造路径)。

因此，在维基百科的文章中，它返回到所有顶点的距离，以及路径中的前一个顶点是什么以获得路径。

P.S.如果你想为面试做准备，我建议你不要再看随机的github回复(可能真的很难理解某个人的代码，这可能是错误的/次优的)，而是打开一本书，试着理解算法背后的逻辑。特别是如果算法可以写成< 50行。