다익스트라 알고리즘 개념

다익스트라 알고리즘은 다이나믹 프로그래밍을 활용한 대표적인 최단거리 알고리즘이다.

최단거리 알고리즘의 사용 예시로 도시의 지도에서 출발지에서 목적지 사이의 거리 중 가장 짧은 거리를 찾는 네비게이션이나, 인공위성 GPS 소프트웨어 등이 있다. 다익스트라 알고리즘은 음의 간선을 포함할 수 없기 때문에 모든 가중치가 양수여야만 한다

다익스트라 알고리즘 실행 순서

1. 모든 정점을 미방문 상태로 만든 후, 시작 정점을 정한다.
   
   위와 같은 그래프가 있을 경우 시작정점은 0번이라 가정하고, 각 정점까지의 최단거리를 계산할 것이다. 초기에는 거리를 알 수 없으므로 INF(무한대)로 설정한다.

2. 시작정점 0을 방문상태로 처리한 후, 방문 할 수 있는 정점들에 대한 거리를 계산

ex) 시작 정점에서(0) 1로 이동할 경우 이동거리는 5
    시작 정점에서(0) 2로 이동할 경우 이동거리는 3

3. 시작 정점에서 각각의 인접 정점과 연결된 거리 중, 최단 거리를 갖는 정점을 찾는다.(최소 가중치 탐색)

_위 사진에서는 가장 가중치가 적은 2번 정점을 방문하고, 시작정점(0)에서 2번 정점을 거쳐 4번 정점을 가면 기존 거리보다 최단 거리이므로 최단 거리를 갱신한다. (INF -> 11)또한, 시작정점(0)에서 2번을 거쳐 3번 정점을 가면 기존 거리보다 최단 거리이므로 갱신한다 (7 -> 6)

4. 방문하지 않은 정점 중 가중치가 작은 3번을 방문

0번 정점 -> 2번 정점 -> 3번 정점을 거쳐서 4번 정점을 가면 기존 거리보다 최단 거리이므로 갱신 (11 -> 10)

5. 방문하지 않은 정점 중 가중치가 작은 4번 정점을 방문

갱신할 거리가 없으므로 갱신은 안함

6. 방문하지 않은 정점 중 가장 가중치가 작은 1번 정점 방문

갱신할 거리가 없고, 모든 정점을 방문 했으므로 종료

다익스트라 코드

밑에는 JS로 구현한 다익스트라 알고리즘이다.

const Node = function(vertex, weight=0){
  this.vertex = vertex;
  this.weight = weight;
  this.link = null;
}

const Graph = function(size){
  this.graph = Array.from({length: size}, (e,i) => new Node(String.fromCharCode(65+i)));
  
  const insertNode = (v1, v2, w) => {
    const v1Node = new Node(v1, w);
    const v2Node = new Node(v2, w);
    const v1Idx = v1.charCodeAt(0) - 65;
    const v2Idx = v2.charCodeAt(0) - 65;
    let graph1 = this.graph[v1Idx];
    let graph2 = this.graph[v2Idx];

    if(graph1.link === null){
      graph1.link = v2Node;
    }
    else{
      while(graph1.link !== null){
        graph1 = graph1.link;
      }
      graph1.link = v2Node;
    }

    if(graph2.link === null){
      graph2.link = v1Node;
    }
    else{
      while(graph2.link !== null){
        graph2 = graph2.link;
      }
      graph2.link = v1Node;
    }

    return;
  }

  Graph.prototype.insertEdge = function(v1, v2, w){
    insertNode(v1, v2, w);
  }

  Graph.prototype.printGraph = function(){
    //간선 그래프 전체 출력
    for(let i=0; i<size; i++){
      let graph = this.graph[i];
      let print = graph.vertex;
      while(graph.link !== null){
        graph = graph.link;
        print += `--[${graph.weight}]--${graph.vertex}`;
      }
      console.log(print);
    }
  }

  Graph.prototype.getGraph = function(){
    return this.graph;
  }
}

// 매개변수: 힙, 그래프, 이동거리(가중치), 방문여부
const heapPush = (h, g, move, isVisit) => {
  // 다음 그래프가 null이 아닐 때 까지 검사
  while(g.link !== null){
    g = g.link; // 가중치 0(자기 자신)은 넣지 않는다.

    // 방문 유무 검사 하기 위해서
    let idx = g.vertex.charCodeAt(0) - 65;

    // 방문 했을 경우, heap에 push하지 않는다.
    if(!isVisit[idx]){
      // g.weight + move: 여태 이동 가중치(move) + 현재 가중치를
      // 더해준다. 나머지도 같다
      if(!h.length) h.push({v:g.vertex, w:g.weight+move});
      else{
        if(h[0].w > g.weight){
          let temp = h[0];
          h[0] = {v:g.vertex, w:g.weight+move};
          h.push(temp);
        }
        else{
          h.push({v:g.vertex, w:g.weight+move});
        }
      }
    }
  }
}

const heapPop = (h) => {
  //최소 힙 구하기!
  const item = h[0];
  const lastItem = h.pop();
  let idx = 0;

  if(!h.length) return item;

  h[0] = lastItem;
  // 자식 노드 유무 확인! 없으면 더 이상 검사 하지 않음!
  while(h[idx*2+1] || h[idx*2+2]){
    let temp = 0;
    // 왼쪽 자식노드 검사
    if(h[0].w > h[idx*2+1].w){
      temp = h[0];
      h[0] = h[idx*2+1];
      h[idx*2+1] = temp;
      idx = idx*2+1;
    }
    // 오른쪽 자식노드 검사!
    else if(h[idx*2+2] && h[0].w > h[idx*2+2].w){
      temp = h[0];
      h[0] = h[idx*2+2];
      h[idx*2+2] = temp;
      idx = idx*2+2;
    }
    // 왼, 오른쪽 자식노드 둘 다 루트 노드보다 클 경우!
    else
      idx++;
  }
  return item;
}

const dijkstra = (start, graph) => {
  const size = graph.length;  // 정점 개수!
  const isVisit = new Array(size).fill(false); // 정점 개수 만큼 방문처리 유무를 검사하기 위한 배열
  const dist = []; // 거리 배열
  const heap = []; // 힙
  let move = 0;    // 이동 가중치
  let idx = start.charCodeAt(0) - 65;  // 현재 인덱스
  let g = graph[idx];                  // 현재 그래프
  heap.push({v:g.vertex, w:g.weight}); // 시작 그래프 노드 push

  while(heap.length){
    g = heapPop(heap);  //최소 힙에서 루트노드(최솟 값) 꺼내기!
    idx = g.v.charCodeAt(0) - 65; //방문 유무 검사하기 위한 인덱스

    // 방문 되지 않은 정점에 대해서만 작업을 한다.
    if(!isVisit[idx]){
      isVisit[idx] = true;
      move = g.w;
      dist[idx] = move;
      heapPush(heap, graph[idx], move, isVisit);
    }
  }

  console.log(dist);

}


const main = (function(){
    const graph = new Graph(6);

    //간선 만들기
    graph.insertEdge("A", "B", 1);
    graph.insertEdge("A", "C", 9);
    graph.insertEdge("B", "C", 10);
    graph.insertEdge("B", "D", 2);
    graph.insertEdge("C", "D", 5);
    graph.insertEdge("C", "E", 1);
    graph.insertEdge("D", "E", 1);
    graph.insertEdge("E", "F", 2);

    //간선 출력
    console.log("간선 출력");
    graph.printGraph();

    //다익스트라 알고리즘 실행!
    console.log("\nA의 최소 경로 출력")
    dijkstra('A', graph.getGraph());
}());

자료 출처
https://code-lab1.tistory.com/29
https://taesung1993.tistory.com/48