4. 코드 작성

우선 이런 복잡한 프로그램을 작성하려면 뭐부터 시작해야할지 막막하다.
이때 글로 먼저 해야할 것들을 작성해보는것을 강력 추천한다. 언제나 그렇듯 pseudocode를 작성해보자.

Pseudo code

• Setup

  • This function should accept a starting and ending vertex.

  • Create an object (we’ll call it distances) and set each ‘key’ to be every vertex in the adjacency list with a value of infinity, except for the starting vertex which should have a value of 0.

  • After setting a ‘value’ in the distance object, add each vertex with a priority of infinity to the priority queue, except the starting vertex of course, which should have a priority of 0.

  • Create another object called previous and set each key to be every vtx in the adjacency list with a value of null.

  • Last But not least, created object called ‘visited’.

• Start looping as long as there is anything in the priority queue.

  • Dequeue a vtx from the priority queue.

  • set the vtx to be key with value of true in the visited obj.

  • If that vtx is the same as the ending vtx – we are done!.

  • Otherwise, mark the vtx as visited and loop through each value(neighbor(s)) in the adjacency list at that vtx.

    • If the neighbors have been visited, continue.

    • Otherwise,

      • update the previous object to contain the vtx.

      • Calculate the distance to that vtx from the starting vtx.

      • If the distance is less than what is currently stored in our distances object.

        • update the distances object with new lower distance.

        • enqueue the vtx with the total distance from the start node.

히~~하!! 도전된다!! 기억해야할것! 여기선 priority queue를 쓴다. 가장 거리가 적은게 먼저 빠져나가야하기 때문이다. 그럼 setup부터 일단 적어보자.

4-1. SetUp code

// 대박.... 이번에 또 해냄... 이건 진짜 못해낼 줄 알았는데 해냄...
// 정말 자랑스럽다 고생했다.
 dijkstra(start, end) {
    //settings
    var distance = {};
    var previous = {};
    var visited = {};
    var result = {
      order: [],
      shortestDistance: 0,
    };

    var pq = new PriorityQueue();

    var chosenVtx;
    for (var vtx in this.adjacencyList) {
      // for loop이 실행 안 됨
      // of 를 사용해서 그럼.
      if (vtx === start) {
        distance[vtx] = 0;
        pq.enqueue(vtx, 0);
      } else {
        // 이거 맞나??
        // 그래 맞다.
        distance[vtx] = Infinity;
        pq.enqueue(vtx, Infinity);
      }

      previous[vtx] = null;
    }
 }

세팅은 다되었고 looping만 하면 된다.

4-2. looping 코드 작성

dijkstra(start, end) {
// setting 코드 생략

// looping
  while (simpleP.size) {
    chosenVtx = simpleP.dequeue(); // a c ...
    if (chosenVtx.val === end) break;

    visited[chosenVtx.val] = true;
    // console.log('while');
    for (var nei of this.adjacencyList[chosenVtx.val]) {
      if (visited[nei.node]) {
        continue;
      } else {
        previous[nei.node] = chosenVtx.val;
        // 여기서 막힘 distance를 어떻게 구하지?
        var sumDistance = this.sumDistance(previous, nei.node); // 4 ...
        if (sumDistance < distance[nei.node]) {
          distance[nei.node] = sumDistance;
          simpleP.enqueue(nei.node, sumDistance);
        }
      }
    }
  }

  // 최단거리랑 그 과정을 return해라
  var startNode = end;
  var nextNode = previous[startNode];
  while (nextNode) {
    // 또는 result.order 라고 해도 된다. 접근하는 방법이 두 가지 구나
    result['order'].push(startNode);
    startNode = nextNode;
    nextNode = previous[startNode];
  }
  result['order'].push(start);
  result['order'].reverse();
  result.shortestDistance = distance[end];

  return {
    distance: distance,
    previous: previous,
    queue: simpleP,
    result: result,
  };
}

이때 거리의 합을 구하는 코드를 구하는데 애를 좀 먹었다. sumDistance 메소드인데 따로 적었다.

// 가장 고심한 부분
sumDistance(previous, start) {
  var startNode = start; // b

  var nextNode = previous[startNode]; // a
  var distance = 0;

  while (nextNode) {
    // console.log(startNode, nextNode);
    for (var node of this.adjacencyList[startNode]) {
      if (node.node === nextNode) {
        distance += node.weight;
      }
    }
    startNode = nextNode; //d c a ...
    nextNode = previous[nextNode]; //c a ...
  }
  return distance;
}

previous obj와 현재 노드를 넘겨주었다.

이제 다 되었다!! 실행시켜보자!! 그럼 아주 잘 된다.

result는 아래와 같이 나온다.

result: {
  order: ["a", "c", "d", "f", "e"];
  shortestDistance: 6;
}

사실 colt의 답이 훨씬 짧긴하지만 이해하기는 어렵다. 반면 내 코드는 pseudocode의 절차를 그대로 따랐기 때문에 debugger를 통해서 dijkstra 알고리즘을 이해하기가 더 쉽다. 따라서 그냥 내 코드만 남겨놓을려고 한다.

다음글에서 마지막 챕터인 Dynamic programming에 대해서 배워보자.