기본 콘텐츠로 건너뛰기

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

이 블로그의 인기 게시물

meteor로 nw.js 개발하기.

실제로 nw.js 어플리케이션을 개발하다보면 UI구현하기 막막하고 수동으로 리프레쉬 하는 것도 귀찮아서 Meteor 연동을 하려고 했더니 생각보다 간단했다.

디렉토리 구조는 먼저 이렇게 잡았다.
`- app
  `-client
  `-public
`- dist
  `- 배포용 html,css,js
  `- package.json
`- package.json 아이디어는 이렇다. nw.js의 시작페이지를 http://localhost:3000으로 두고 배포시엔 meteor client 배포툴인 meteor-build-client를 사용하여 html,css,js 로 분리하는 계획이다.

가장 중요한 nw.js 용 package.json 파일은 아래와 같이 구성한다.
{
  "main": "http://localhost:3000",
  "node-remote": "http://localhost:3000",
  "name": "<앱이름>"
} 이게 전부. 어떻게 보면 Web과 nw.js를 동시에 개발할 수도 있는 환경이기도 한 것이다.
meteor create app 을 해서 meteor용 앱을 만들고 meteor 를 시작한다.
그리고, 위의 package.json이 있는 경로로 돌아가서 nw . 으로 nwjs를 실행한다.

한번 번쩍하더니 잘 된다.
cordova 등에서 index.html 대신 http://localhost:3000을 하는 것도 비슷한 느낌이다.

즐겁게 개발을 일단 마구 하고 실제로 배포하기 위해서는 개발환경이 아니라 html,css,js로 구성된 배포본을 만들어야한다.
npm install -g 해도 되지만 어짜피 Meteor에서만 쓸거
meteor npm install -g meteor-build-client 해버릴거다.

개발은 문제 없어 보이고 배포판을 한번 만들어보자. meteor app 이 있는 경로(meteor run으로 …

RxJS - ReactiveX 인터뷰

A: 왜 RxJS입니까
B: javascript는 참 쉽고 친숙한 언어죠.
A: 별로 그렇게 생각 안합니다만.
B: 그래서 좀 어렵고 있어보이는게 뭘까 싶어서...
A: 네?
B: 함수형이라는게 유행하기도 하고
f(x) 좋쟎습니까? 미스테리~ 미스테리~ 정수정짱짱 으아아

이런 수학선생님이라면 수포자 따윈 A: ...
B: 그리고 반응형이라는 말 뭔가
A: 뭔가?
B: 대충대충해도 막 알아서 할거 같고...
A: 그럴리가요?
B: 안그렇겠죠?
A: 네
B: 네

(잠시만 기다려주세요)

A: 그래도 뭔가 매력이 있으니 이렇게 시간을 내셔서 이것저것 Rx에 대해 글도 쓰고 이야기도 하고 그러시는거 아닌가요?
B: 매력이라.
으음.
제가 팔꿈치 터널 증후근이 좀 있어요.
오른손 세끼손가락, 약지손가락이 저립니다.
A: 무슨 상관이?
B: 그래서 각종 괄호를 쓰는게 너무 힘듭니다.
소중대괄호 만든 사람 죽었으면.
Hello world (ASCII): https://esolangs.org/wiki/Parenthesis_Hell
A: 이미 옛날에 돌아가셨겠죠.
B: 그렇겠네요.
아무튼 그래서 소중대괄호 의존이 적은 커피스크립트를 쓰는데요.
A: 빨리 본론을 말씀해주시죠.
B: 커피스크립트에서 가로로 80자 이상쓰면 Line exceeds maximum allowed length 라고 경고해요.
A: 그래서요?
B: 근데 Rx를 쓰면 코드를 가늘게 쓸 수가 있더라구요.
A: 호오?
B: 그리고 = 쓰는 것도 너무 힘듭니다.
A: 네?
B: 오른손을 쓰쟎아요.
A: ...
그러니까 정리하면
1. 괄호가 힘들다
2. 커피를 쓴다
3. 커피는 길게 쓰면 경고
4. Rx를 쓰면 코드가 가늘다
5. 대입문을 줄이고 싶다.
B: 네
하지만 5번은 생각보다 별로...
A:
B:

B: 아!
A: ?
B: 코드가 가늘어서 좋은 점이.
A: 네.
B: 핸드폰에서 코드를 보기 좋습니다.
A: ... 왜 팔꿈치 터널 증후근이 안 낫는지 알겠습니다.
B: 도와주세요.
쇠고기 사묵으면 나을 것 같습니…

Troubleshooting - Meteor package가 적용이 되지 않을 때

버전 1.5 기준 package.js에서 Package.onUse 에 새 패키지를 추가했는데 인식하지 못하는 경우가 있다.
Package.onUse((api) => {
  api.use([
    'vulcan:core',
    'vulcan:forms',
    'vulcan:accounts' /* <-- 추가함! */
  ]);
...
} 내부패키지건 원격패키지건 안되는 안된다. 이럴 때 meteor add 후 meteor remove 해도 되지만 더 간단한 방법이 있다. meteor update vulcan:accounts 이렇게 update 해주는 방법이 있다. .meteor/package 파일을 건들지 않아서 좋다. 그래도 역시 좋지 않다. Meteor 스럽지 않다. https://github.com/meteor/meteor/issues/7721 현재 1.5.2에서도 해결이 안되었군요. 해결되어 적용되면 다시 글 올리겠습니다.