let input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
let VE = input[0].split(' ')
let v = +VE[0]
let startV = +input[1]
let uvws = []
for (let i = 2; i < input.length; i++) {
uvws.push(input[i].split(' ').map((e) => +e))
}
let linkedInfo = (uvws) => {
let links = Array(v + 1)
uvws.forEach((edge) => {
if (!links[edge[0]]) links[edge[0]] = []
links[edge[0]].push({
vertex: edge[1],
cost: edge[2]
})
})
return links
}
class MinHeap {
constructor() {
this.nodes = []
}
insert(value) {
this.nodes.push(value)
this.bubbleUp()
}
bubbleUp(index = this.nodes.length - 1) {
if (index < 1) return;
const currentNode = this.nodes[index]
const parentIndex = Math.floor((index - 1) / 2)
const parentNode = this.nodes[parentIndex]
if (parentNode.cost <= currentNode.cost) return;
this.nodes[index] = parentNode
this.nodes[parentIndex] = currentNode
index = parentIndex
this.bubbleUp(index)
}
extract() {
const min = this.nodes[0]
if(this.nodes.length === 1){
this.nodes.pop();
return min;
};
this.nodes[0] = this.nodes.pop()
this.trickleDown();
return min
}
trickleDown(index = 0) {
const leftChildIndex = 2 * index + 1
const rightChildIndex = 2 * index + 2
const length = this.nodes.length
let minimum = index
if(!this.nodes[rightChildIndex] && !this.nodes[leftChildIndex]) return;
if(!this.nodes[rightChildIndex]){
if(this.nodes[leftChildIndex].cost < this.nodes[minimum].cost){
minimum = leftChildIndex;
}
return;
}
if(this.nodes[leftChildIndex].cost > this.nodes[rightChildIndex].cost){
if (rightChildIndex <= length && this.nodes[rightChildIndex].cost < this.nodes[minimum].cost) {
minimum = rightChildIndex
}
}else{
if (leftChildIndex <= length && this.nodes[leftChildIndex].cost < this.nodes[minimum].cost) {
minimum = leftChildIndex
}
}
if (minimum !== index) {
let t = this.nodes[minimum]
this.nodes[minimum] = this.nodes[index]
this.nodes[index] = t
this.trickleDown(minimum)
}
}
}
let dijkstra = (links, startV) => {
let shortestPathTable = Array(v + 1).fill(Infinity)
shortestPathTable[0] = -1
shortestPathTable[startV] = 0
let minHeap = new MinHeap()
const start = {
vertex: startV,
cost: 0
};
minHeap.insert(start);
while (minHeap.nodes.length) {
const selected = minHeap.extract();
const startVertex = selected.vertex,
beforeCost = selected.cost;
if (links[startVertex] === undefined) continue;
if (shortestPathTable[startVertex] < beforeCost) continue;
links[startVertex].forEach((edge) => {
const {
vertex,
cost
} = edge
if (shortestPathTable[vertex] <= shortestPathTable[startVertex] + cost) return;
shortestPathTable[vertex] = shortestPathTable[startVertex] + cost
const next = {
vertex,
cost: shortestPathTable[startVertex] + cost
};
minHeap.insert(next)
})
}
return shortestPathTable
}
let printAll = (shortestPathTable) => {
let answer = ''
for (let i = 1; i < shortestPathTable.length; i++) {
if (shortestPathTable[i] === Infinity) answer += 'INF' + '\n'
else answer += shortestPathTable[i] + "" + '\n'
}
console.log(answer.trim())
}
let links = linkedInfo(uvws);
let table = dijkstra(links, startV)
printAll(table)
1. 힙을 사용한다.
입력으로 들어오는 데이터 개수가 많기 때문에 힙을 사용하지 않으면 시간초과가 난다.
- 최소 힙을 구현한다.
- 비용에 따라 배치한다.
- 부모노드는 자식노드보다 비용이 더 작다.
2. 다익스트라 알고리즘을 사용한다.
- 최단거리 테이블을 만든다.
- 힙에서 값을 하나씩 빼며 거리를 계산한다.
가장 먼저, 최단거리 테이블에서 시작정점에 해당하는 index와 cost를 힙에 삽입한다.
2-1. 최단거리 테이블의 index, cost 값과 힙에서 뺀 vertex, cost값을 비교하여
- 힙에서 뺀 vertex가 연결된 정점이 없으면 continue
- 힙에서 뺀 cost가 최단거리 테이블의 cost보다 크면 continue
- 힙에서 뺀 vertex를 거쳐갈 때 cost가 같거나 더 커지면 continue
- 그렇지 않으면 해당 vertex를 거쳐갈 때의 cost를 최단거리 테이블의 cost로 바꾼다.
2-2. 최단거리 테이블에서 값이 바뀐 애들을 힙에 삽입한다.
2-3. 위 과정을 힙의 길이가 0이 될때까지 반복한다
3. 최단거리 테이블 내 cost들을 출력한다.