[이코테 - 다익스트라 알고리즘/ 플로이드워셜 알고리즘]

페이지 239 - 개선된 다익스트라 알고리즘

var obj = {}


var hye = [
 [1, 2, 2],
 [1, 3, 5],
 [1, 4, 1],
 [2, 3, 3],
 [2, 4, 2],
 [3, 2, 3],
 [3, 6, 5],
 [4, 3, 3],
 [4, 5, 1],
 [5, 3, 1],
 [5, 6, 2]

]


var quque = [];

var obj_form = {};

var check_node = [];

for (var i = 0; i < hye.length; i++) {

 if ((Object.keys(obj).includes(hye[i][0].toString())) == false) {

  obj[hye[i][0]] = [hye[i].slice(1, 3)];
  obj_form[hye[i][0]] = 100;
 }

 else {
  obj[hye[i][0]].push(hye[i].slice(1, 3));
 }

}
obj_form[6] = 100;
console.log(obj_form)
quque.push([1, 0]);
obj_form[1]=0
console.log(obj,obj_form)
while (quque.length > 0) {
 console.log(quque.slice())
 var [node, gari] = quque.shift();

 console.log(node, gari)
 
 if (check_node.includes(node) == false && obj[node]) {

  for (var i = 0; i < obj[node].length; i++) {
   var best =obj[node][i];
   console.log(best)
   var [nnode, ggari]=best
   if (gari + ggari < obj_form[nnode]) {
    obj_form[nnode] = gari + ggari;
    console.log(obj_form,'확인좀')
    quque.push([nnode, ggari + gari])
   }

  }
  quque.sort((a, b) => {
   return a[1] - b[1];
  })
  check_node.push(node);
 }



}


console.log(obj_form,'마지막')

해석 그대로 따라서 작성 하였다.

page 257

<<미래도시 >>
n과 m 이 100 이기 때문에
플로이드 와샬 알고리즘을 사용해도 되는 문제이다.

const fold = function (arv) {

var obj = Array.from(new Array(6), () => new Array(6).fill(100));
console.log(obj)
for (var i = 0; i < arv.length; i++){
var [x, y] = arv[i];

obj[x][y] = 1;
obj[x][x] = 0;

obj[y][x] = 1;
이것을 추가해서 완료 시켰다.
양방향성인것을 감안해서 설계하면된다.

}

for (var i = 1; i < 6; i++){
//첫번째로 사용하는 노드는 무엇인가?
for (var z = 1; z < 6; z++){
for (var zz = 1; zz < 6; zz++){

if (z != i && zz != i && z!=zz) {

  var yey = Math.min(
   obj[z][zz], (obj[z][i]+ obj[i][zz])
 )
 
 obj[z][zz] = yey
}


 //obj[z][zz]=yey.slice()

}
}

}
console.log(obj[1][5]+obj[5][4])

}

const arr = [
[1, 2,],
[1, 3],
[1, 4],
[2, 4],
[3, 4],
[3, 5],
[4,5]
]
fold(arr)