기본 콘텐츠로 건너뛰기

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

라벨:

댓글

댓글 쓰기

이 블로그의 인기 게시물

cURL로 cookie를 다루는 법

http://stackoverflow.com/questions/22252226/passport-local-strategy-and-curl 레거시 소스를 보다보면 인증 관련해서 cookie를 사용하는 경우가 있는데 가령 REST 서버인 경우 curl -H "Content-Type: application/json" -X POST -d '{"email": "aaa@bbb.com", "pw": "cccc"}' "http://localhost/login" 이렇게 로그인이 성공이 했더라도 curl -H "Content-Type: application/json" -X GET -d '' "http://localhost/accounts/" 이런 식으로 했을 때 쿠키를 사용한다면 당연히 인증 오류가 날 것이다. curl의 --cookie-jar 와 --cookie 옵션을 사용해서 cookie를 저장하고 꺼내쓰자. 각각 옵션 뒤엔 저장하고 꺼내쓸 파일이름을 임의로 지정하면 된다. 위의 과정을 다시 수정해서 적용하면 curl -H --cookie-jar jarfile "Content-Type: application/json" -X POST -d '{"email": "aaa@bbb.com", "pw": "cccc"}' "http://localhost/login" curl -H --cookie jarfile "Content-Type: application/json" -X GET -d '' "http://localhost/accounts/" 이렇게 사용하면
댓글 쓰기
자세한 내용 보기

MQTT 접속해제 - LWT(Last will and testament)

통신에서 중요하지만 구현이 까다로운 문제로 "상대방이 예상치 못한 상황으로 인하여 접속이 끊어졌을때"의 처리가 있다. 이것이 까다로운 이유는 상대방이 의도적으로 접속을 종료한 경우는 접속 종료 직전에 자신의 종료 여부를 알리고 나갈 수 있지만 프로그램 오류/네트웍 연결 강제 종료와 같은 의도치 않은 상황에선 자신의 종료를 알릴 수 있는 방법 자체가 없기 때문이다. 그래서 전통적 방식으로는 자신의 생존 여부를 계속 ping을 통해 서버가 물어보고 timeout 시간안에 pong이 안올 경우 서버에서 접속 종료를 인식하는 번거로운 방식을 취하는데 MQTT의 경우 subscribe 시점에서 자신이 접속 종료가 되었을 때 특정 topic으로 지정한 메시지를 보내도록 미리 설정할 수 있다. 이를 LWT(Last will and testament) 라고 한다. 선언을 먼저하고 브로커가 처리하게 하는 방식인 것이다. Last Will And Testament 라는 말 자체도 흥미롭다. 법률용어인데  http://www.investopedia.com/terms/l/last-will-and-testament.asp 대략 내가 죽으면 뒷산 xx평은 작은 아들에게 물려주고 어쩌고 하는 상속 문서 같은 내용이다. 즉, 내가 죽었을(연결이 끊어졌을) 때에 변호사(MQTT Broker - ex. mosquitto/mosca/rabbitMQ등)로 하여금 나의 유언(메시지)를 상속자(해당 토픽에 가입한 subscriber)에게 전달한다라는 의미가 된다. MQTT Client 가 있다면 한번 실습해보자. 여러가지가 있겠지만 다른 글에서처럼  https://www.npmjs.com/package/mqtt  을 사용하도록 한다. npm install mqtt --save 로 설치해도 되고 내 경우는 자주 사용하는 편이어서 npm install -g mqtt 로 전역설치를 했다. 호스트는 무료 제공하고 있는 test.mosquitto.org 를
댓글 쓰기
자세한 내용 보기

MQTT Broker Mosquitto 설치 후 설정

우분투 기준 $ sudo apt-add-repository ppa:mosquitto-dev/mosquitto-ppa $ sudo apt-get update 하고 $ sudo apt-get install mosquitto 으로 설치하면 서비스까지 착실하게 올라간다. 설치는 간단한데 사용자를 만들어야한다. /etc/mosquitto/mosquitto.conf 파일에서 권한 설정을 변경하자. allow_anonymous false 를 추가해서 아무나 못들어오게 하자. $ service mosquitto restart 서비스를 재시작. 이제 사용자를 추가하자. mosquitto_passwd <암호파일 경로명> <사용자명> 하면 쉽게 만들 수 있다. # mosquitto_passwd /etc/mosquitto/passwd admin Password:  Reenter password:  암호 넣어준다. 두번 넣어준다. 이제 MQTT 약을 열심히 팔아서 Broker 사글세방 임대업을 하자.
댓글 쓰기
자세한 내용 보기