javascript - 获取两点之间的最短路径

Question

我有以下数组:

steps=[
    {from:1, to:8},
    {from:1, to:2},
    {from:2, to:7},
    {from:7, to:9},
    {from:8, to:9}
];

这个数组是描述它在两点之间有连接的地方。例如从 1 到 7 有一种方式 1->2->7。

在 JavaScript 中，我如何生成例如从 1 到 9 的最短路径？

已更新

function calc_route(start, end, data)
    {           
        console.log(start+", "+end);
        console.log(data);              
        for(var i=0; i<data.length; i++)
        {

            if(data[i].topoint == end && data[i].frompoint == start)
            {
                console.log("Return");                  
                console.log(data[i]);
                return data[i];
            }
            else
            {
                if(data[i].frompoint == start)
                {                       
                    calcfor =   data.splice(i, 1);                                      
                    calc_route(calcfor[0].topoint, end, data);
                }
            }
        }
    }

这是我到目前为止所做的，我的问题是如何保存路径？

Answer 1

寻找最低成本路径的标准方法是 A* algorithm (可以使用启发式知识)或 Dijkstra's Algorithm (不能)。这两个链接都有可以轻松转换为 Javascript 的伪代码。