자바스크립트로 구현하는 그래프 최단 경로 알고리즘: 가중치 엣지 추가하기

그래프 이론에서 최단 경로 문제(Shortest Path Problem)란 그래프에 존재하는 두 정점(vertex 또는 node) 사이를 연결하는 경로 중, 경로를 구성하는 간선(edge)들의 가중치 합이 최소가 되는 경로를 찾는 문제를 말합니다.

최단 경로 알고리즘을 구현하려면 기존의 엣지 추가 메서드들이 단순히 노드 간 연결만 처리하던 것에서 한 단계 더 나아가, 각 간선에 가중치(weight)도 함께 저장할 수 있어야 합니다. 이를 위해 addEdge와 addDirectedEdge 메서드를 수정해 보겠습니다.

가중치를 지원하는 엣지 추가 메서드

아래 코드는 양방향 엣지와 단방향 엣지에 가중치를 추가하는 방법을 보여줍니다.

1. 양방향 엣지 추가 (addEdge)

/**
 * 두 노드 사이에 동일한 가중치의 양방향 엣지를 추가합니다.
 *
 *            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 });
}

2. 단방향 엣지 추가 (addDirectedEdge)

/**
 * 다음과 같은 방향성 엣지를 추가합니다.
 *
 *            weight
 * node1 ----------------> node2
 */
addDirectedEdge(node1, node2, weight = 1) {
    this.edges[node1].push({ node: node2, weight: weight });
}

3. 그래프 출력 (display)

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

기본 가중치 값의 활용

위 코드의 핵심은 매개변수에 설정된 weight = 1이라는 기본값(default parameter)입니다. 그래프에 엣지를 추가할 때 가중치를 명시적으로 지정하지 않으면, 해당 엣지에는 자동으로 기본 가중치 1이 할당됩니다.

이러한 설계는 여러모로 유용합니다. 예를 들어 가중치 개념이 없는 일반적인 그래프 탐색(BFS, DFS 등)에서는 모든 간선의 비용을 동일하게 취급하면 되므로 기본값 1이 자연스럽게 적용되고, 반면 다익스트라(Dijkstra)나 벨만-포드(Bellman-Ford) 같은 최단 경로 알고리즘에서는 실제 비용에 맞는 가중치를 직접 전달하면 됩니다.

이제 가중치 정보를 포함한 그래프 구조가 준비되었으므로, 이를 바탕으로 본격적인 최단 경로 알고리즘을 구현할 수 있습니다.