Skip to content

Instantly share code, notes, and snippets.

@hsjoihs
Created March 26, 2018 12:08
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save hsjoihs/c241b0d1ae2039cf67a5aec77d2ba223 to your computer and use it in GitHub Desktop.
Save hsjoihs/c241b0d1ae2039cf67a5aec77d2ba223 to your computer and use it in GitHub Desktop.
「友達がなんかオリジナルのDijkstra法を改良できたっぽいのでコード見てもらえますか?」というDMが来た、嘘解法っぽさあるけど反例分からん
/* DMで相談がきたソースコード */
/*
id:{image:'path',cost:INF,done:[],route:"",positionX:"latitude",positionY:"elevation",positionZ:"longitude",links:["link_1","link_0"]}
costに頂点に到達するまでのコスト、doneで最短距離を調べ終わったやつ、
routeに最短距離でどの頂点から来たか、positionXに緯度、
positionYに高度、positionZに経度、
linksに配列でその頂点につながってる頂点
*/
var maplist;
dijInit("id0","id2");
function dijInit(start, goal){
maplist[start].cost = 0;
maplist[start].done = maplist[start].links;
dijkstra(start,goal);
res(goal,start);
}
function res(point,start){
var route = [];
while(true){
route.push(point);
if(point==start){
break;
}else{
point = maplist[point].route;
}
}
console.log(route);
}
function dijkstra(point,goal){
console.log(point);
for (var i = 0; i < maplist[point].links.length; i++) {
let linked = maplist[point].links[i];
let x = (maplist[point].positionX-maplist[linked].positionX)*1.1;
let y = (maplist[point].positionY-maplist[linked].positionY)*0.00001;
let z = (maplist[point].positionZ-maplist[linked].positionZ)*0.9;
var cost = maplist[point].cost + Math.sqrt(x*x + y*y + z*z);
if((cost < maplist[linked].cost) && (-1 == maplist[linked].done.indexOf(point))){
maplist[linked].cost=cost;
maplist[linked].route=point;
maplist[linked].done.push(point);
dijkstra(linked,goal);
}
}
}
function mapInit(){
let INF = Infinity;
maplist = {
id:{image:'path',cost:INF,done:[],route:"",positionX:"latitude",positionY:"elevation",positionZ:"longitude",links:["link_1","link_0"]}
};
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment