2013년 11월 13일 수요일

다익스트라(Dijkstra) 구현하기

매번 정리해야지 하면서 하지 못했던것들을 조금씩 블로그에 기록하고 있습니다.
정리가 우선이기 때문에 보시는 분들에게 설명이 부족할것이라는 생각이 들었습니다.

그래서 간단한 변명을 하려고 합니다.
우연찮게 이 곳을 들리시는 분들이 몇분이라도 드물지만 계시는 것 같습니다.
나중에 시간이 되면 이곳에 올린 내용을 정리해 보겠습니다.
여기 올리는 내용은 알고리즘을 설명하기 보다는 구현 내용에 치중하고 있어서
자세한 설명을 생략하고 있습니다.

최단 거리를 찾는 알고리즘입니다.
결국 시작점에서 부터 연결되는 모든 지점을 찾아 최소거리를 확인하고
확인하는 시점에 경로를 기록해 두는 것이중심이 된 알고리즘입니다.

경로를 구성하는 방법은 Matrix 인데 Random 함수로 거리를 산정했습니다.
그 후는 Dijkstra 알고리즘에 의해 거리를 구하고 경로를 구하는 방법을 구현해 보았습니다.

다음은 소스 입니다.

function makeRandomDistanceMatrix(maxSize,connSize,maxDistance) {
// check arguments ... skip
var result = [];
var seed = Math.round(maxDistance/1000);
for ( var y = 0; y < maxSize; y++ ) {
var arr = [];
for ( var x = 0; x < maxSize; x++ ) {
var cPos = Math.round(x/2);
if ( (y-cPos) >= 0 && (y+cPos) < maxSize ) {
if ( x%2 == 0) {
cPos = y+cPos;
} else {
cPos = y-cPos;
}
} else if ( (y-cPos) < 0 ) {
cPos = x;
} else {
cPos = (maxSize-x-1);
}

if ( cPos == y ) {
arr[cPos] = 0;
} else {
if ( x < connSize ) {
arr[cPos] = Math.round(Math.random()*seed)*x;
} else {
arr[cPos] = maxDistance;
}
}
}
result.push(arr);
//document.write(arr+"<BR>");
}
return result;
}

function dijkstraFn(matrix,start,end,maxDistance) {
// check arguments ... skip
var size = matrix.length;
var distance = [];
var visit = [];
var path = [];
var result = [];
for ( var i = 0; i < size; i++ ) {
distance[i] = maxDistance;
visit[i] = 0;
path[i] = -1;
}
// set the start point..
distance[start] = 0;

for ( var y = 0; y < size; y++ ) {
var minDistance = maxDistance;
var cPos = -1;
for ( var x = 0; x < size; x++ ) {
if ( visit[x] == 0 && distance[x] < minDistance ) {
cPos = x;
minDistance = distance[x];
}
}
if ( cPos == -1 ) {
break;
}
visit[cPos] = 1;
for ( var x = 0; x < size; x++ ) {
//skip start point ..
if ( distance[x] > 0 && distance[x] > ( distance[cPos] + matrix[cPos][x] ) ) {
distance[x] = ( distance[cPos] + matrix[cPos][x] );
// x 접점에 가장 가까운 포인트를 설정
path[x] = cPos;
}
}
}

//alert ( path.join() );

result.push(end);
while( path[end] != -1 ) {
end = path[end];
result.push(end);
}

result.reverse();

var resultMx = [];
var st = result[0];
var sumDist = 0.0;

var arr2 = [];
arr2.push("DIST");
arr2.push(distance.join());
resultMx.push(arr2);
arr2 = [];
arr2.push("PATH");
arr2.push(result.join());
resultMx.push(arr2);

arr2 = [];
arr2.push(st);
arr2.push(0);
resultMx.push(arr2);
for ( var i = 1; i < result.length; i++ ) {
arr2 = [];
var ed = result[i];
arr2.push(ed);
arr2.push(matrix[st][ed]);
sumDist += matrix[st][ed];
st = ed;
resultMx.push(arr2);
}

arr2 = [];
arr2.push("T_DIST");
arr2.push(sumDist);
resultMx.push(arr2);

return resultMx;
}

function drawTableTmp(matrixTbl) {
var tableObj = document.createElement("TABLE");
tableObj.style.backgroundColor = "#000080";
tableObj.style.tableLayout = "fixed";
tableObj.setAttribute("cellSpacing","1");
tableObj.setAttribute("cellPadding","0");
var tBodyObj = document.createElement("TBODY");
tableObj.appendChild(tBodyObj);
var size = matrixTbl.length;
for ( var y = 0; y < size; y++ ) {
var trObj = document.createElement("TR");
trObj.style.height = "22px";
tBodyObj.appendChild(trObj);
for ( var x = 0,xSize=matrixTbl[y].length; x < xSize; x++ ) {
var tdObj = document.createElement("TD");
tdObj.style.width = "100px";
tdObj.style.backgroundColor = "#FFFFFF";
tdObj.innerText = matrixTbl[y][x];
trObj.appendChild(tdObj);
}
}
document.body.appendChild(tableObj);
}

window.onload = function() {
var maxSize = 14;
var connSize = 8;
var maxDistance = 99999999;
var matrix = makeRandomDistanceMatrix(maxSize,connSize,maxDistance);
var start = 1;
var end = maxSize-2;
var realPath = dijkstraFn(matrix,start,end,maxDistance);

drawTableTmp(matrix);

drawTableTmp(realPath);
}


실행해 볼 수 있는 소스입니다.

Random 함수라 그때 그때 달라 지지만 아래는 결과 입니다.
09925673060144105167852429055240384136297999999999999999999999999999999999999999999999999
1629301210303973217588848020018645091546999999999999999999999999999999999999999999999999
249129565830139936339416361645186468256319999999999999999999999999999999999999999999999999
183830838247002065416302336411780613676999999999999999999999999999999999999999999999999
1763934205453843642297011784250384226356999999999999999999999999999999999999999999999999
9999999968555931792517496639370625563147525048349999999999999999999999999999999999999999
99999999999999995590903221052646188924506544035821214307099999999999999999999999999999999
999999999999999999999999136668259060221022311050174768370000298410999999999999999999999999
999999999999999999999999999999992998803607352871422298101477841204483762729999999999999999
999999999999999999999999999999999999999939489112655512399327991017802639837641035899999999
999999999999999999999999999999999999999999999999607012613602226429433011448486744228378
999999999999999999999999999999999999999999999999295722278970196490251391323470589562984
999999999999999999999999999999999999999999999999407680233490215635185468265302344780191114
9999999999999999999999999999999999999999999999994901968292687785138120163947141286601550
DIST16293,0,86734,39732,105148,211896,122651,91546,266314,265721,386762,501246,473506,504230
PATH1,7,8,10,12
10
791546
8174768
10120448
1286744
T_DIST473506

1에서 12까지의 경로는 1->7->8->10->12 로 이어지고 있습니다.

작성자: 시간:

댓글 없음:

댓글 쓰기

피드 구독하기: 댓글 (Atom)