[JS] 최단 거리 알고리즘

❗️다익스트라 알고리즘 (Dijkstra)

• 가중치를 가진 그래프에서 최단 경로를 탐색하는 알고리즘 (BFS)
• 가중치가 양수값을 가질 경우에만 사용 가능
• 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 계산
• 최단 거리가 여러개의 최단 거리로 이루어져있음 (dp이용)

✅ 구현 방식

dp= [] // 출발 노드에서 각 노드까지의 최단거리 저장
visited = [] // 방문했는지를 체크

1. 출발 노드에서 출발 노드는 거리 0, dp[start] = 0
2. 출발 노드와 직접 연결된 노드까지의 거리를 dp에 저장
3. dp상 가장 작은 값을 가지면서 방문하지 않은 노드 방문

순차탐색을 이용한 구현의 단점
- 다음 탐색 노드를 선택할때 앞에서부터 찾기 때문에 시간복잡도 O(N^2)
- 우선순위 큐를 이용해서 O(logN) 시간 복잡도로 줄임

✅ javascript 구현

let graph = Array.from(Array(V + 1), () => []);
input.forEach((el) => {
  let [from, to, weight] = el;
  graph[from].push([to, weight]);
});

let distance = Array(V + 1).fill(Infinity);
let visited = Array(V + 1).fill(0);
visited[0] = 1;
distance[start] = 0;

let queue = new Minheap();
queue.push([start, 0]);
while (queue.size() > 0) {
  let [cur, w] = queue.shift();

  for (nextNode of graph[cur]) {
    let [next, weight] = nextNode;
    let tmp = distance[cur] + weight;
    if (distance[next] > tmp) {
      distance[next] = tmp;
      queue.push([next, distance[next]]);
    }
  }
}

❗️벨만 포드 알고리즘 (Bellman-Ford)

• 가중치가 음수일 경우에도 사용할 수 있는 최단거리 알고리즘
• 우선순위큐를 사용하지 않고 간선들의 집합 edges를 사용

✅ 백준 11657번 - 타임머신

let dir = __dirname + "/11657.txt";
const path = process.platform === "linux" ? "./dev/stdin" : dir;
const line = require("fs").readFileSync(path, "utf-8");
let input = line.trim().split("\n");

let [V, E] = input.shift().split(" ").map(Number);
input = input.map((el) => el.split(" ").map(Number));

let distance = Array(V + 1).fill(Infinity);

function bellman(start) {
  distance[start] = 0;

  for (let i = 0; i < V; i++) {
    for (let j = 0; j < E; j++) {
      let [cur, next, nextDistance] = input[j];

      if (
        distance[cur] !== Infinity &&
        distance[next] > distance[cur] + nextDistance
      ) {
        distance[next] = distance[cur] + nextDistance;
        if (i === V - 1) {
          return true;
        }
      }
    }
  }
  return false;
}
let answer = [];
let negativeCycle = bellman(1);
if (negativeCycle) console.log(-1);
else {
  for (let i = 2; i < V + 1; i++) {
    if (distance[i] === Infinity) answer.push(-1);
    else {
      answer.push(distance[i]);
    }
  }
}
console.log(answer.join("\n"));

❗️플로이드 워셜 알고리즘 (Floyd-Warshall)

• 전체 쌍 최단 경로 문제

✅ 백준 11404 - 플로이드

let dir = __dirname + "/11404.txt";
const path = process.platform === "linux" ? "./dev/stdin" : dir;
const line = require("fs").readFileSync(path, "utf-8");
let input = line.trim().split("\n");

const V = +input.shift();
const E = +input.shift();
input = input.map((el) => el.split(" ").map(Number));

// 모든 쌍의 비용을 체크, 초기에는 Infinity로 초기화
let cost = Array.from(Array(V + 1), () => Array(V + 1).fill(Infinity));
// 자기 자신으로 가는 비용은 0
for (let i = 1; i <= V; i++) {
  cost[i][i] = 0;
}

// 초기 상태의 정점에서 인접한 노드만 확인
input.forEach((el) => {
  let [from, to, c] = el;
  if (cost[from][to] > cost[from][from] + c) {
    cost[from][to] = cost[from][from] + c;
  }
});

for (let mid = 1; mid <= V; mid++) {
  // 거쳐지는 지점
  for (let start = 1; start <= V; start++) {
    // 시작지점
    for (let end = 1; end <= V; end++) {
      // 도착지점
      if (cost[start][mid] + cost[mid][end] < cost[start][end]) {
        cost[start][end] = cost[start][mid] + cost[mid][end];
      }
    }
  }
}

// 못가는 경로 0으로 체크
for (let start = 1; start <= V; start++) {
  for (let end = 1; end <= V; end++) {
    if (cost[start][end] === Infinity) {
      cost[start][end] = 0;
    }
  }
}
cost = cost.slice(1).map((el) => el.slice(1));
console.log(cost.map((arr) => arr.join(" ")).join("\n"));