2012-01-15 4 views
0

У меня есть следующий массив:Получить кратчайший путь между двумя точками

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); 
       } 
      } 
     } 
    } 

Это то, что я сделал до сих пор, мой вопрос, как я могу сохранить путь?

+1

В общем, кажется, что Вы хотите, поиск график. Я бы посмотрел на алгоритм dijkstra и A * (A Star) – rsaxvc

ответ

0

Вот решение:

function calc_route(start, end, data, mypath, solution) 
     {    
      mypath.push(parseInt(start)); 
      for(var i=0; i<data.length; i++) 
      { 

       if(data[i].topoint == end && data[i].frompoint == start) 
       { 
        mypath.push(end); 
        solution.push(mypath); 
        return end; 
       } 
       else 
       { 

        if(data[i].frompoint == start) 
        {         
         calcfor = data.slice(0); 
         calcfor.splice(i,1);          
         calc_route(data[i].topoint, end, calcfor, mypath.slice(0), solution); 
        } 
       } 
      } 
     } 
7

Стандартный способ поиска наиболее дешевых дорожек - либо A* algorithm (который может использовать эвристические знания), либо Dijkstra's Algorithm (что не может). Обе эти ссылки имеют псевдокод, который можно легко преобразовать в Javascript.

Смежные вопросы