JavaScript - 通過圖中數百個節點的最短路徑

我想知道如何計算許多節點內的最短路徑到根節點，但我不知道如何以正確的方式做到這一點。節點以某種方式相互連接，因此始終有多條路徑通向根節點。JavaScript - 通過圖中數百個節點的最短路徑

我有所有節點一個js對象，這裏是一個片段，如果它：

var nodes = { 
11420 : {  // no out, but many other nodes have 11420 in their out 
    out : [] 
}, 
18866 : { 
    out : [11420] 
}, 
739 : { 
    out : [18866] 
}, 
1957 : { 
    out : [739] 
}, 
33296 : { 
    out : [1957, 36774] 
}, 
57264 : { 
    out : [33296] 
}, 
54447 : {  // root 
    out : [57264] 
}, 
37569 : { 
    out : [36542, 57264] 
} 
// ... 1500 nodes more

}

我如何計算的最短路徑爲讓說節點11420根54447？結果應該是具有節點ID的數組。

謝謝。

來源

2015-10-04 eScoo

[JavaScript中最短路徑（HTTP的可能重複：// stackoverflow.com/questions/32527026/shortest-path-in-javascript） –

Demo在演示有它的這種縮小的一個代號：https://raw.githubusercontent.com/andrewhayward/dijkstra/master/graph.js

var nodes = 
{ 
    "11420" : 
    {  
     "18866":1    
    }, 
    "18866" : 
    { 
     "11420":1, 
     "739":1    
    }, 
    "739" : 
    { 
     "18866":1, 
     "1957":1     
    }, 
    "1957" : 
    { 
     "739":1 , 
     "33296":1 
    }, 
    "33296" : 
    { 
     "1957":1, 
     "36774":1, 
     "57264":1 
    }, 
    "57264" : 
    { 
     "33296":1, 
     "54447" :1 
    }, 
    "54447" : 
    { 
     "57264":1 
    }, 
    "37569" : 
    { 
     "36542":1, 
     "57264":1 
    } 
}; 

var graph = new Graph(nodes); 
var result = graph.findShortestPath('11420', '54447'); 
console.log(result); 

$("#yoo").html("["+result.join()+"]");

來源

2015-10-04 16:51:34 Diptox

非常感謝，這就是我一直在尋找的東西。作品像一個魅力:) – eScoo

不客氣：D – Diptox

在Djikstra's Algorithm上閱讀，瞭解圖中節點的最短路徑。 This page似乎有一個很好的描述。一般算法基於加權圖（如果連接兩個節點，則存在與遍歷節點之間的邊相關的「權重」或「成本」）;你的情況，你可以假設每個重爲1

來源

2015-10-04 16:30:04 keithmo

JavaScript - 通過圖中數百個節點的最短路徑

回答

相關問題