자바 스크립트로 다익스트라 알고리즘 구현

다익스트라 알고리즘은 그래프 내의 한 정점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘입니다. 다음은 자바스크립트로 다익스트라 알고리즘을 구현한 예시와 해당 코드의 설명입니다.

구현:

class PriorityQueue {
  constructor() {
    this.values = [];
  }

  enqueue(val, priority) {
    this.values.push({ val, priority });
    this.sort();
  }

  dequeue() {
    return this.values.shift();
  }

  sort() {
    this.values.sort((a, b) => a.priority - b.priority);
  }
}

class WeightedGraph {
  constructor() {
    this.adjacencyList = {};
  }

  addVertex(vertex) {
    if (!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
  }

  addEdge(vertex1, vertex2, weight) {
    this.adjacencyList[vertex1].push({ node: vertex2, weight });
    this.adjacencyList[vertex2].push({ node: vertex1, weight });
  }

  Dijkstra(start, finish) {
    const nodes = new PriorityQueue();
    const distances = {};
    const previous = {};
    let path = [];
    let smallest;

    for (let vertex in this.adjacencyList) {
      if (vertex === start) {
        distances[vertex] = 0;
        nodes.enqueue(vertex, 0);
      } else {
        distances[vertex] = Infinity;
        nodes.enqueue(vertex, Infinity);
      }
      previous[vertex] = null;
    }

    while (nodes.values.length) {
      smallest = nodes.dequeue().val;
      if (smallest === finish) {
        while (previous[smallest]) {
          path.push(smallest);
          smallest = previous[smallest];
        }
        break;
      }

      if (smallest || distances[smallest] !== Infinity) {
        for (let neighbor in this.adjacencyList[smallest]) {
          let nextNode = this.adjacencyList[smallest][neighbor];
          let candidate = distances[smallest] + nextNode.weight;
          let nextNeighbor = nextNode.node;

          if (candidate < distances[nextNeighbor]) {
            distances[nextNeighbor] = candidate;
            previous[nextNeighbor] = smallest;
            nodes.enqueue(nextNeighbor, candidate);
          }
        }
      }
    }
    return path.concat(smallest).reverse();
  }
}

설명:

1. PriorityQueue: 우선순위 큐를 구현한 클래스입니다. 이 큐는 다익스트라 알고리즘에서 가장 짧은 거리의 정점을 빠르게 찾기 위해 사용됩니다.
2. WeightedGraph: 가중치가 있는 그래프를 나타내는 클래스입니다.
3. addVertex: 그래프에 정점을 추가하는 메서드입니다.
4. addEdge: 그래프에 간선과 그 간선의 가중치를 추가하는 메서드입니다.
5. Dijkstra: 다익스트라 알고리즘을 구현한 메서드입니다. 시작 정점과 종료 정점을 인수로 받아서 시작 정점에서 종료 정점까지의 최단 경로를 배열로 반환합니다.

이 코드는 간선의 가중치가 양수일 때만 작동합니다. 만약 음수 가중치의 간선이 있다면, 다른 알고리즘을 사용해야 합니다.