javascript - 给定边权时两个火车站之间的最短路径

Question

我必须找到火车站之间的最短距离——

给出的是代表火车站的节点，边被认为是距离。我必须计算最小距离。我使用的逻辑有一些错误。

这是我尝试过的代码。但我没有得到两点之间的最短路径。 实现它：控制台： var e=new calc_route("1","3",steps) 解决方案应该给我 1 和 3 之间的最小距离.....例如可能有从 1 到 2 的路径wgt 5 和 2 到 3 总共 wgt 4 是 9。在 1 到 3 之间可能存在 wgt 10 的直接路径。那么应该选择第一条路径

steps=[
    {from:1, to:8},
    {from:1, to:2},
    {from:2, to:7},
    {from:7, to:9},
    {from:8, to: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].to == end && data[i].from == start)
        {
            console.log("Return");                  
            console.log(data[i]);
            return data[i];
        }
        else
        {
            if(data[i].from == start)
            {                       
                calcfor =   data.splice(i, 1);                                      
                calc_route(calcfor[0].topoint, end, data);
            }
        }
    }
}

Answer 1

你应该看看 Dijkstra 的算法。http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

在 javascript 中找到它的实现，并重用已经测试过的代码。

Answer 2

似乎您需要实现的是 A* 算法... http://en.wikipedia.org/wiki/A*_search_algorithm 一个快速的谷歌会给你很多已经实现的结果。