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的算法應該返回什麼？

回答

相關問題