최단 경로 찾기

최단 경로 찾기

간편 큐를 사용한 다익스트라의 알고리즘

const graph = {
  A: ["B", "C"],
  B: ["A", "D", "E"],
  C: ["A", "F"],
  D: ["B"],
  E: ["B", "F"],
  F: ["C", "E"],
};

const SimplePriorityQueue = {
  init: function () {
    this.values = [];
  },
  enqueue: function (name, priority) {
    this.values.push({ name, priority });
    this.values.sort((a, b) => a.priority - b.priority);
    return this.values;
  },
  dequeue: function () {
    return this.values.shift();
  },
};

function findShortestWay(start, end) {
  const distance = {};
  const visitedHash = {};
  const previous = {};
  for (const key in graph) {
    distance[key] = key == start ? 0 : Infinity;
    previous[key] = null;
  }
  const spq = Object.create(SimplePriorityQueue);
  spq.init();
  spq.enqueue(start, 0);

  while (true) {
    const dequeued = spq.dequeue().name;
    if (dequeued == end) {
      break;
    }
    const neighbors = graph[dequeued];
    for (const currentNeighbor of neighbors) {
      if (visitedHash.hasOwnProperty(currentNeighbor)) {
        continue;
      }
      const distanceFromStart = distance[dequeued] + 1;
      //가중치 없으니 노드 간의 거리는 무조건 1
      if (distanceFromStart < distance[currentNeighbor]) {
        distance[currentNeighbor] = distanceFromStart;
        previous[currentNeighbor] = dequeued;
        spq.enqueue(currentNeighbor, distanceFromStart);
      }
      debugger;
    }
    visitedHash[dequeued] = true;
  }
  let node = end;
  const route = [];
  while (node) {
    route.unshift(node);
    node = previous[node];
  }
  return route;
}

const result = findShortestWay("A", "F");

• 시간복잡도를 생각하면 우선순위 큐를 직접 구현해서 사용하는 게 맞겠으나 과연 실전에서 우선순위 큐를 구현하고 있을 시간이 있을지는 모르겠다.

• 그러니 일단 간편 큐로 구현하고 만약 시간이 남는다면 우선순위 큐를 구현하는 게 맞을 듯 싶다.

우선순위 큐를 사용한 다익스트라의 알고리즘

const graph = {
  A: ["B", "C"],
  B: ["A", "D", "E"],
  C: ["A", "F"],
  D: ["B"],
  E: ["B", "F"],
  F: ["C", "E"],
};

const Node = {
  init: function (name, priority) {
    this.name = name;
    this.priority = priority;
  },
};

const PriorityQueue = {
  init: function () {
    this.values = [];
  },
  enqueue: function (name, priority) {
    const newNode = Object.create(Node);
    newNode.init(name, priority);

    this.values.push(newNode);
    let idxOfNewNode = this.values.length - 1;
    while (idxOfNewNode > 0) {
      const idxOfParent = Math.floor((idxOfNewNode - 1) / 2);
      const parentNode = this.values[idxOfParent];
      if (parentNode.priority > newNode.priority) {
        this.values[idxOfParent] = newNode;
        this.values[idxOfNewNode] = parentNode;
        idxOfNewNode = idxOfParent;
      }
      break;
    }
    return this.values;
  },
  dequeue: function () {
    if (this.values.length == 0) {
      return;
    }

    if (this.values.length == 1) {
      return this.values.pop();
    }
    const last = this.values.pop();
    const dequeued = this.values[0];
    this.values[0] = last;
    let idxOfLast = 0;

    while (true) {
      const idxOfLeftChild = 2 * idxOfLast + 1;
      const idxOfRightChild = 2 * idxOfLast + 2;
      const leftChild = this.values[idxOfLeftChild];
      const rightChild = this.values[idxOfRightChild];

      function swap(direction) {
        const child = direction == "left" ? leftChild : rightChild;
        const idxOfChild =
          direction == "left" ? idxOfLeftChild : idxOfRightChild;
        this.values[idxOfLast] = child;
        this.values[idxOfChild] = last;
        idxOfLast = idxOfChild;
      }

      // 양쪽 자식이 다 없을 때
      if (!leftChild) {
        return dequeued;
      }

      // 오른쪽 자식만 없을 떄
      if (!rightChild) {
        if (leftChild.priority < last.priority) {
          swap.call(this, "left");
          continue;
        }
        return dequeued;
      }

      // 양쪽 자식이 다 있는데, 두 자식의 우선순위가 같을 때
      if (leftChild.priority == rightChild.priority) {
        swap.call(this, "left");
        // 어느 쪽으로 스왑해도 무방
        continue;
      }

      // 양쪽 자식이 다 있을 때 && 왼쪽으로 스왑해야 할 때
      if (
        leftChild.priority < rightChild.priority &&
        leftChild.priority < last.priority
      ) {
        swap.call(this, "left");
        continue;
      }

      // 양쪽 자식이 다 있을 때 && 오른쪽으로 스왑해야 할 때
      if (
        rightChild.priority < leftChild.priority &&
        rightChild.priority < last.priority
      ) {
        swap.call(this, "right");
        continue;
      }
    }
  },
};

const pq = Object.create(PriorityQueue);

function findShortestWay(start, end) {
  const distance = {};
  const visitedHash = {};
  const previous = {};
  for (const key in graph) {
    distance[key] = key == start ? 0 : Infinity;
    previous[key] = null;
  }
  pq.init();
  pq.enqueue(start, 0);

  while (true) {
    const dequeued = pq.dequeue().name;
    if (dequeued == end) {
      break;
    }
    const neighbors = graph[dequeued];
    for (const currentNeighbor of neighbors) {
      if (visitedHash.hasOwnProperty(currentNeighbor)) {
        continue;
      }
      const distanceFromStart = distance[dequeued] + 1;
      //가중치 없으니 노드 간의 거리는 무조건 1
      if (distanceFromStart < distance[currentNeighbor]) {
        distance[currentNeighbor] = distanceFromStart;
        previous[currentNeighbor] = dequeued;
        pq.enqueue(currentNeighbor, distanceFromStart);
      }
      debugger;
    }
    visitedHash[dequeued] = true;
  }
  let node = end;
  const route = [];
  while (node) {
    route.unshift(node);
    node = previous[node];
  }
  return route;
}

const result = findShortestWay("A", "F");
console.log(result);

• 이걸 실전에서 할 수 있을까;;