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

http://en.wikipedia.org/wiki/Dijkstra's_algorithm

여기가 위키.

언제나처럼 소스는 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);

});