Dijkstra的算法应该返回什么？

-1

我是一名前端Javascript开发人员，但想学习一些图论以准备Google面试，我查阅了Dijkstra算法的一些实现。Dijkstra的算法应该返回什么？

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

我试图修改GitHub的例子，以配合维基百科伪和返回的距离似乎给最短的数值距离分别来自startVertex ...但上一个没有返回的最短路径

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 }

来源

2016-03-06 WinchenzoMagnifico

此实现似乎的最短路径的长度从给定的节点返回到每一个节点，在这种情况下'S'。 – mrmcgreg

根据你的需要，它可以返回路径和/或路径中所有顶点的总和。 – Mox

什么是prev应该在wikipedia pseudocode？ – WinchenzoMagnifico

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

有许多不同的修改。您可以返回两个节点之间的距离，节点与所有其他节点之间的距离，距离和路径，距离和前一个节点（足以构建路径）。

所以在维基百科文章的情况下 - 它返回你距离把所有的顶点，什么是在路径中前顶点，让您的路径。

P.S.如果要准备面试，我建议你停止寻找随机github上回购协议（也可能是真的很难了解一个特定的人，这可能是错误/次优的代码），而是打开一本书，并尝试了解算法背后的逻辑。特别是如果算法可以写在< 50行。

来源

2016-03-06 03:03:29

我试图寻找了算法CLRS但那是更难不是看实际的代码 - 东西理解的是那些50行中的一行，其实需要的不仅仅是一个行更是实施 – WinchenzoMagnifico

Dijkstra的算法应该返回什么？

回答

相关问题