다익스트라 알고리즘

• Graph 내 최단경로 문제 정의와 활용분야 및 다익스트라 알고리즘의 핵심 아이디어를 이해한다.
• 다익스트라 알고리즘과 복잡도

1. Graph 최단경로 알고리즘

• 지하철의 최단경로나 네비게이션에서 쓰인다.
  
• 위의 그림을 예로 들어, 교차로를 중심으로 해서 각 도로를 그래프로 모델링하고 각 도로를 지나가는데 걸리는 시간 그리고 거리 등등을 다 edge에 weight화함으로써 출발지와 도착지를 설정하면 출발지부터 도착지까지 가는 최단경로를 계산해서 우리에게 알려준다.
• 이것을 푸는 과정의 대표적인 방법은 다익스트라 알고리즘!
• 그 외에도 플로이드 워셜 알고리즘, 벨만포드 알고리즘 등이 있다.
• 프림 알고리즘과 굉장히 유사!(다음에 프림 알고리즘도 공부해 보자.)
• 다익스트라 알고리즘은 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘.
• 번외로 플로이드 워셜 알고리즘은 모든 지점에 다른 모든 지점까지의 최단경로를 모두 구해야 하는 경우.
• 시작점으로 이게 최단 경로라고 보장할수 있는 것들을 하나씩 차즘 늘려가는 방식이며 실제로 구현과 아이디어 자체가 프림 알고리즘과 유사.
• 프림알고리즘도 미니멈 스패닝트리를 하나씩 확정되는 것부터 확장해나가는 방식이라고 하면, 다익스트라도 마찬가지로 출발점부터 최단경로를 하나씩 확정해나가기 때문에.

2. 다익스트라 알고리즘 구현

• 모든 꼭지점을 미방문 상태로 초기화
• 시작 vertex를 정함
• 시작 vertex를 visit했다고 처리
• 시작점에 인점한 vertex로 가는 모든 거리값을 기록
• 정점A에 각각의 인접 정점과 연결된 거리 중에서, 최단 거리를 갖는 정점을 찾는다(최소 weight 탐색)
• 최단 거리를 갖는 경로를 통해 다음 정점으로 이동한다.
• 이동 거리를 기록
• 다음 정점을 B라고 가정하면, 정점 B에 인접한 정점으로 가는 모든 거리값에 이동거리를 더한 값과 그 전에 기록된 최단거리값을 서로 비교해서 이때 최소값을 갖는 거리를 기록
• 방문했던 정점을 visit 처리
• 모든 vertex를 visit할 때까지 위의 과정 반복.
• 시간복잡도

기본버전은 O(N2)

// 인접행렬 방식으로 구하기

const INF = Infinity;
const arr = [
[0, 2, 5, 1, INF, INF],
[2, 0, 3, 2, INF, INF],
[5, 3, 0, 3, 1, 5],
[1, 2, 3, 0, 1, INF],
[INF, INF, 1, 1, 0, 2],
[INF, INF, 5, INF, 2, 0]
];
const isVisit = new Array(6).fill(false);

const getMin = function(vertex){
let min = INF;
let idx = 0;
for(let i=0; i<vertex.length; i++){
  if(min > vertex[i] && !isVisit[i]){
    min = vertex[i];
    idx = i;
  }
}
return idx;
}

const dist = function(start){
let v = arr[start-1];
let count = 0;
let end = v.length;
let min = 0;
let startV = v;
isVisit[start-1] = true;

while(count < end){
  const idx = getMin(startV);
  min += startV[idx];
  const next = arr[idx];
  for(let i=0; i<v.length; i++){
    if(v[i] > next[i]+min && !isVisit[i])
      v[i] = next[i]+min;
  }
  startV = arr[idx];
  isVisit[idx] = true;
  count++;
}
console.log(v);
}

const main = (function(){
dist(1);
}());

최소힙에 기반한 건 O(변의 개수+ Nlog2N)

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());
}());