[바미] Graph algorithm - Dijkstra의 최단 경로 알고리즘 구현하기.

Dijkstra의 최단 경로 알고리즘?

Dijkstra의 최단 경로 알고리즘은 그래프에서 출발점에서부터 다른 모든 정점까지의 최단 경로를 찾는 알고리즘인데요.

이 알고리즘은 음의 가중치를 가진 간선을 허용하지 않아요.

음의 가중치

음의 가중치(negative weight)는 그래프에서 간선의 가중치가 음수인 경우를 말하는데 일반적으로 Dijkstra의 최단 경로 알고리즘은 음의 가중치가 없는 그래프에서 사용되고 있어요.
그 이유는 음의 가중치가 있는 경우에 최단 경로를 찾는 문제에서 최적해가 아닐 수 있기 때문이죠.

음의 가중치가 있는 그래프에서 시작 노드와 도착 노드 사이의 최단 경로를 찾는 문제를 생각할 때 만약 음의 가중치가 있는 경로가 최단 경로가 되는 경우, Dijkstra 알고리즘은 최단 경로를 찾지 못할 수 있어요.
이러한 경우에는 벨만-포드(Bellman-Ford) 알고리즘와 같은 복잡한 알고리즘이 필요하게 되죠.

 

코드 구현

// 그래프 클래스 정의
class Graph {
  constructor() {
    this.nodes = new Set();
    this.edges = new Map();
    this.distances = new Map();
  }

  // 노드 추가
  addNode(node) {
    this.nodes.add(node);
    this.edges.set(node, new Set());
  }

  // 간선 추가
  addEdge(node1, node2, distance) {
    this.edges.get(node1).add(node2);
    this.distances.set(`${node1}-${node2}`, distance);
  }

  // 최단 경로 찾기
  dijkstra(startNode) {
    let visited = new Set();
    let distances = new Map();
    let predecessors = new Map();

    distances.set(startNode, 0);
    predecessors.set(startNode, null);

    let queue = new PriorityQueue();
    queue.add(startNode, 0);

    for (let node of this.nodes) {
      if (node !== startNode) {
        distances.set(node, Infinity);
        predecessors.set(node, null);
      }
    }

    while (!queue.isEmpty()) {
      let current = queue.poll();

      if (visited.has(current)) {
        continue;
      }

      visited.add(current);

      for (let neighbor of this.edges.get(current)) {
        let distance = this.distances.get(`${current}-${neighbor}`);
        let totalDistance = distances.get(current) + distance;

        if (totalDistance < distances.get(neighbor)) {
          distances.set(neighbor, totalDistance);
          predecessors.set(neighbor, current);
          queue.add(neighbor, totalDistance);
        }
      }
    }

    return { distances, predecessors };
  }
}

// 우선순위 큐 클래스 정의
class PriorityQueue {
  constructor() {
    this.elements = [];
  }

  // 큐가 비어있는지 확인
  isEmpty() {
    return this.elements.length === 0;
  }

  // 큐에 노드 추가
  add(node, priority) {
    this.elements.push({ node, priority });
    this.elements.sort((a, b) => a.priority - b.priority);
  }

  // 우선순위가 가장 높은 노드 추출
  poll() {
    return this.elements.shift().node;
  }
}

// 사용 예시
let graph = new Graph();
graph.addNode('A');
graph.addNode('B');
graph.addNode('C');
graph.addNode('D');
graph.addNode('E');

graph.addEdge('A', 'B', 4);
graph.addEdge('A', 'C', 2);
graph.addEdge('B', 'C', 1);
graph.addEdge('B', 'D', 5);
graph.addEdge('C', 'D', 8);
graph.addEdge('C', 'E', 10);
graph.addEdge('D', 'E', 2);

let result = graph.dijkstra('A');
console.log(result.distances); // Map { 'A' => 0, 'B' => 3, 'C' => 2, '

코드 설명

Graph 클래스는 노드와 간선, 그리고 거리를 저장하는 Set, Map으로 구성되는데 먼저, addNode 메소드를 사용하여 노드를 추가하고, addEdge 메소드를 사용하여 두 노드 간의 간선과 거리를 추가하였어요.

dijkstra 메소드는 시작 노드를 인자로 받아 해당 노드에서부터 다른 노드들까지의 최단 경로와 그 경로를 구성하는 노드들을 반환하게 되는데 이를 위해 우선순위 큐를 사용하여 다음으로 방문할 노드를 정하고, 방문한 노드는 visited Set에 저장하여 중복 방문을 막도록 하였어요.

 

마지막으로, distances와 predecessors Map을 반환하는데 distances Map은 시작 노드에서부터 각 노드까지의 최단 거리를 저장하고, predecessors Map은 해당 노드까지의 최단 경로를 구성하는 직전 노드를 저장하는 Map이에요.

구현한 코드에서는 A를 시작 노드로 설정하고, 각 노드와 간선을 추가한 후, dijkstra 메소드를 호출하여 최단 경로를 구하며 결과는 다음과 같아요.

 

Map {
  'A' => 0,
  'B' => 3,
  'C' => 2,
  'D' => 8,
  'E' => 10
}

즉, A에서 B까지의 최단 거리는 4가 아니라 3임을 알 수 있죠.