자바 스크립트 - 그래프 순회 - 최단 경로 복귀

Question

그래프를 탐색하고 싶습니다.

var Node = function(name) { 
    this.edge_list = []; 
    this.name = name; 
}; 

및

var Graph = function() { 
    this.node_list = []; 
}; 

에지가과 같이 노드에 추가됩니다 :

Node.prototype.addEdge = function(end, distance) { 
    this.edge_list.push({end, distance}); 
}; 

그래프는 다음과 같습니다

start: 
[ Object { end: '1', distance: 13 }, 
    Object { end: '2', distance: 14 } ] 
1: 
[ Object { end: 'start', distance: 13 }, 
    Object { end: '3', distance: 2 } ] 
2: 
[ Object { end: 'start', distance: 14 }, 
    Object { end: '3', distance: 1 } ] 
3: 
[ Object { end: '1', distance: 2 }, 
    Object { end: '2', distance: 1 }, 
    Object { end: 'end', distance: 10 } ] 
end: 
[ Object { end: '3', distance: 10 } ] 

나는 두 구조를 가지고

내가하고 싶은 것은 함수를 만드는 것이다. source에서 target까지의 최단 거리/경로를 반환합니다.

나는 현재 거리가 긍정적 인 경우에, 다 익스트라가 갈 수있는 방법입니다 https://repl.it/C6Fh

Answer 1

까지 테스트가 있습니다. 그러나, 매우 간단한 알고리즘은 다음

• 마르크 무한 거리를 갖는 각 노드
• 0의 거리를 갖는 소스 노드로 수행 소스부터 그래프 너비 우선 탐색은 : 노드의 거리가 현재 에지가 작은 거리
• 시킨다면
  • 업데이트 큐

의 단부 노드를 추가

다음은 Node 클래스의 이전 노드와 거리를 저장하는 빠른 솔루션입니다.

dstNode.distance과 같이 노드 자체에서 최소 거리를 찾을 수 있습니다. 경로의 경우 dstNode에서 추적하고 prev 링크를 따르십시오.

function shortest_path(g, src, dst) { 
    var get_node = function(n) { 
     for (var i = 0; i < g.node_list.length; i++) { 
      if (g.node_list[i].name == n) { 
       return g.node_list[i]; 
      } 
     } 
     return null; 
    } 

    var srcNode = get_node(src); 
    var dstNode = get_node(dst); 
    for(var i = 0; i < g.node_list.length; i++) { 
     // think of as infinity (currently assumed to be unreachable) 
     g.node_list[i].distance = 2147483647; 
     g.node_list[i].prev = null; 
    } 
    srcNode.distance = 0; // src node is of distance zero from itself 

    q = [srcNode]; // we will breadth-first traverse the graph 
    while (q.length > 0) { 
     var cur = q[0]; 
     q.shift(); 
     for (var i = 0; i < cur.edge_list.length; i++) { 
      n = get_node(cur.edge_list[i].end); 
      // here we are looping through neighbors of cur 
      // to see if a smaller distance exists 
      if (n.distance > cur.distance + cur.edge_list[i].distance) { 
       n.distance = cur.distance + cur.edge_list[i].distance; 
       n.prev = cur; 
       q.push(n); 
      } 
     } 
    } 
}