기본 콘텐츠로 건너뛰기

Dijkstra's algorithm을 이용한 최단 경로 찾기를 javascript 로 구현해보았다.

여기가 위키.

언제나처럼 소스는 http://jsbin.com/acatav/3/edit#javascript
"최단경로 그까이꺼 대충 트리로 펼친 담에 올 합산한 비용이 젤 적은 놈 뽑아내면 되는거 아니야?"
라고 생각했다가 역시 검색이 최고. 나보다 멍청한 놈은 좀처럼 없다는 것이 진리.
알고리즘은 심플하다.
'자신과 인접한 노드와 이제까지 탐색한 노드 중 가까운 놈만 남기고 다 지운다.'의 반복.
node 에서 해보려면 맨 마지막 $('p')부분을 지워주시면 되겠다.
사용예는 다음과 같다.
computePath(vertices, vertices[0]);
vertices 중 0번째부터 출발하는 최단 경로를 계산해서 각 vertex별 previous 와 minDistance를 넣어준다.
node.js 에서 바로 돌려볼 수 있는 소스는 다음과 같다.

var vertex = function(param){
  var name = '';
  var edge = [];
  var minDistance = 99999;
  var previous = null;
  name = name || param.name;
  edge = edge || param.edge;
  minDistance = minDistance || param.minDistance;
  previous = previous || param.previous;
  return {
    "name" : name,
    "edge" : edge,
    "minDistance" : minDistance,
    "previous" : previous
  };
};
var vertices = [];
vertices.push(new vertex({"name" : 'Harrisburg'})); // Baltimore,Allentown
vertices.push(new vertex({"name" : 'Baltimore'})); // Harrisburg
vertices.push(new vertex({"name" : 'Washington'})); // Baltimore
vertices.push(new vertex({"name" : 'Philadelphia'})); // Baltimore,Allentown,New York
vertices.push(new vertex({"name" : 'Binghamton'})); // Allentown
vertices.push(new vertex({"name" : 'Allentown'})); // Harrisburg,Philadelphia,Binghamton,New York
vertices.push(new vertex({"name" : 'New York'})); // Philadelphia,Allentown
vertices[0].edge = [{
      "id" : vertices[1],
      "distance" : 79.83
    },{
      "id" : vertices[5],
      "distance" : 81.15
    }];
vertices[1].edge = [{
      "id" : vertices[0],
      "distance" : 79.75
    },{
      "id" : vertices[2],
      "distance" : 39.42
    },{
      "id" : vertices[3],
      "distance" : 103.00
    }];
vertices[2].edge = [{
      "id" : vertices[1],
      "distance" : 38.65
    }];
vertices[3].edge = [{
      "id" : vertices[1],
      "distance" : 102.53
    },{
      "id" : vertices[5],
      "distance" : 61.44
    },{
      "id" : vertices[6],
      "distance" : 96.79
    }];
vertices[4].edge = [{
      "id" : vertices[5],
      "distance" : 133.04
    }];
vertices[5].edge = [{
      "id" : vertices[0],
      "distance" : 102.53
    },{
      "id" : vertices[3],
      "distance" : 62.05
    },{
      "id" : vertices[4],
      "distance" : 134.47
    },{
      "id" : vertices[6],
      "distance" : 91.63
    }];
vertices[6].edge = [{
      "id" : vertices[3],
      "distance" : 97.24
    },{
      "id" : vertices[5],
      "distance" : 87.94
    }];
var computePath=function(vertices, source) {
  source.minDistance = 0;
  var vertexQueue = [source];
  while (vertexQueue.length) {
    var u = vertexQueue.shift(0);
    console.log('-----');
    console.log(u.name);
    u.edge.forEach(function(v,k) {
      var distanceThroughU = u.minDistance + v.distance;
      console.log('    ', v.id.name + ':'+distanceThroughU+'<'+v.id.minDistance + 
                  (distanceThroughU < v.id.minDistance ? '' : '(out)' ));
      if(distanceThroughU < v.id.minDistance) {
        v.id.minDistance = distanceThroughU;
        v.id.previous = u;
        vertexQueue.push(v.id);
      }
    });
  }
};
computePath(vertices, vertices[0]);
vertices.forEach(function(v) {
  var path = [];
  var current = v.previous;
  while(!!current) {
    path.push(current);
    current = current.previous;
  }
  var result = v.name+':'+path.map(function(w) {
    return w.name;
  }).reverse().join('->')+'=>'+v.name+'('+v.minDistance+')';
  console.log(result);
});

이 블로그의 인기 게시물

ESP32 DevBoard 개봉기

오늘 드디어 손에 넣었다. ESP32 DevBoard!
Adafruit 에서 15개 한정 재입고 트윗을 보고 광속 결제.
그리고 1주일의 기다림. 사랑해요 USPS <3
알리를 이용하다보니 1주일 정도는 광속 배송임.
물론 배송비도 무자비함 -_ㅜ
15개 한정판 adafruit 발 dev board
그놈이 틀림없으렸다.
오오 강려크한 포스
ESP32_Core_board_V2라고 적혀있군요.
ESP32 맞구요. 네네. ESP32-D0WDQ6 라고 써있는데 D → Dual-core 0 → No internal flash W → Wi-Fi D → Dual-mode Bluetooth Q → Quad Flat No-leads (QFN) package 6 → 6 mm × 6 mm package body size 라고 함.
길이는 이정도
모듈크기는 이정도
코어는 6mm밖에 안해! 여기에 전기만 넣으면 BLE+WIFI!
밑에 크고 발 8개 달린 놈은 FM25Q32라고 32Mbit 플래시메모리
ESP8266 DevBoard 동생이랑 비교 크고 아름다운 레귤레이터랑 CP2102 USB Driver가 붙어있음.
ESP8266 DevBoard엔 CH340G 인데 확 작아졌네.
머리를 맞대어 보았음.
모듈크기는 아주 약간 ESP32가 더 큰데 워낙에 핀이 많고 촘촘함. ESP8266인 ESP12는 핀 간격이 2.00mm인데 비해
ESP32는 1.27mm 밖에 안함.
딱봐도 비교가 될 정도.
https://www.sparkfun.com/news/2017 크고 아름다운 Pinouts

ESP8266 보드랑 별로 안달라보인다.
http://www.silabs.com/products/mcu/pages/usbtouartbridgevcpdrivers.aspx#mac
에서 CP2102 드라이버를 설치하고
screen 으로 연결해보자.
내 경우엔 tty.SLAB_USBtoUART 로 잡혔다.
어디서 기본 속도가 115200bps 라고 들은 적이 있어서
screen /dev/tty.SLAB_USBtoUART …

즐거운 Online Prototyping Tool 들

jsbin, codepen, jsfiddle 이런 것들은 일단 생략. 너무 유명한 것들이라.

https://launchpad.graphql.com - node.js 기반 graphQL 연습장. 이것만으로도 충분히 훌륭한 백엔드
https://codesandbox.io/ npm 사용이 가능한 클라이언트 사이드 연습장. webpackbin이 너무 문제가 많아서 찾아본 것.

https://scrimba.com 이건 codesandbox+ asciinema(https://asciinema.org/) 같은 느낌인데 키 녹화와 음성 녹화 기능이 추가되었다. 다 좋은데 화살표 키로 빨리감기 뒤로감기 기능이 안되고 익스포트(youtube등)으로 지원이 없는게 아쉽다.

이 둘이 만나면? https://codesandbox.io/s/jvlrl98xw3?from-embed
뭐야 이거 무서워 하지마 ㄷㄷ;  graphql+react-native-web(부왘ㅋㅋ)

https://repl.it/languages 전통을 자랑하는 REPL 도구. 지원 언어 종류가 -_-;;;;;

https://tio.run/# repl.it? 장난함? 얘는 지원 언어가 무려 386종류. J랑 아희도 있다.

https://play.golang.org/ 즐거운 go playground. 소스 포멧팅 넘 좋아.

http://decaffeinate-project.org/repl/ 최고의 coffeescript REPL. 원래 용도는 coffee를 ecma6코드로 바꾸는 것이지만...

https://scaphold.io
https://www.graph.cool/ graphql backend service. scaphold.io는 설치도 필요없는 클라우드. graphcool은 호스팅+클라우드 다있음. 둘 다 막상막하. 푸쉬서버도 되고 뭐 미친득.

https://glitch.com/ gomix에서 결국 glitch로 안착.  node.js

https://www.shadertoy.com 잘하고 싶다! 쉐이다! 오디오도 된다!

http:/…

graphql 연습 /w launchpad

https://launchpad.graphql.com/mw9wkzv99
단순 전체쿼리+조건쿼리+추가

http://graphql.org/graphql-js/passing-arguments/
참고. random ID는 crypto 1.0.1 사용
  type Query {
    Members: [member]
    getMember(id: ID!): member
  }
  type member {
    id: ID!
    text: String
  }
  input memberInput {
    text: String
  }
  type Mutation {
    addMember(member: memberInput): member
  } SQL 정의. facebook 쪽은 스트링에 지지는 거 진짜 좋아하네. *.gql 파일이 있다고 하니 이해해주자.
resolver는 var buffer = [];
const resolvers = {
  Query: {
    Members: (root, args, context) => {
      return buffer;
    },
    getMember: (id)=> {
      return buffer.find(o=>o.id)
    }
  },
  Mutation: {
    addMember(_, {member}) {
      const mm = { ...member, id:randomBytes(10).toString('hex') };
      buffer.push(mm);
      return mm;
    }
  }
}; 평범 평범.
https://dev-blog.apollodata.com/tutorial-graphql-subscriptions-server-side-e51c32dc2951 다음으로 pub/sub 연습.
https://launchpad.graphql.com/xvn94n3ql   type Subscription {
    memberAdded: member
  } member가 added되는 순간을 감시. imp…