Javascript의 최단 경로 알고리즘

그래프 이론에서 최단 경로 문제는 그래프에서 구성 간선의 가중치 합이 최소화되도록 그래프에서 두 정점(또는 노드) 사이의 경로를 찾는 문제입니다. 여기서 우리는 가장자리 추가를 수정하고 가장자리에도 가중치를 추가할 수 있도록 지시된 방법을 추가해야 합니다.

이것을 추가하는 방법을 살펴보겠습니다 -

예시

/**
   * Adds 2 edges with the same weight in either direction
   *
   *             weight
   * node1 <================> node2
   *             weight
   *
*/
addEdge(node1, node2, weight = 1) {
   this.edges[node1].push({ node: node2, weight: weight });
   this.edges[node2].push({ node: node1, weight: weight });
}

/**
   *  Add the following edge:
   *
   *             weight
   * node1 ----------------> node2
   *
*/

addDirectedEdge(node1, node2, weight = 1) {
   this.edges[node1].push({ node: node2, weight: weight });
}

display() {
   let graph = "";
   this.nodes.forEach(node => {
      graph += node + "->" + this.edges[node].map(n => n.node) .join(", ")+ "\n";
   });
   console.log(graph);
}

이제 그래프에 간선을 추가할 때 가중치를 지정하지 않으면 기본 가중치 1이 해당 간선에 할당됩니다. 이제 이것을 사용하여 최단 경로 알고리즘을 구현할 수 있습니다.