こんにちは。
A* search algorithm の Javascript 実装（下記）の利用による最短経路探索で¹ ²、今回は地図表示に Mapbox GL JS を利用し、interactive 風にしてみました。
A* Search Algorithm in JavaScript (Updated) - Brian Grinstead
https://github.com/bgrins/javascript-astar (astar.js)
地図上の二箇所をマウスでクリックすると近傍都市を始点終点とした経路探索が走ります（下記例は始点 Paris、終点 Cannes）。
astar.html
<!DOCTYPE html>
<html>
<meta charset="utf-8">
<script src="astar.js"></script>
<script src="http://d3js.org/d3.v3.min.js"></script>
<script src='https://api.tiles.mapbox.com/mapbox-gl-js/v0.29.0/mapbox-gl.js'></script>
<link href='https://api.tiles.mapbox.com/mapbox-gl-js/v0.29.0/mapbox-gl.css' rel='stylesheet' />
<style>
body { margin:0; padding:0; }
# map { position:absolute; top:0; bottom:0; width:100%; }
svg {
  position: absolute;
  width: 100%;
  height: 100%;
}
circle {
  stroke: #222;
  stroke-width: 0.7px;
}
</style>
</head>
<body>
<div id="map"></div>
<script>
var MILE=1609, KM=1000, RE=6371*KM, DEGREE=Math.PI/180;
var units = {mi: MILE, km: KM};
var mapCenter = [4.0, 46.0], mapScale = 4, unitDistance='km';
var nodes = [
    {name: "Paris", lon: 2.3508, lat: 48.8567},
    {name: "Lyon", lon: 4.84, lat: 45.76},
    {name: "Marseille", lon: 5.37, lat: 43.2964},
    {name: "Bordeaux", lon: -0.58, lat: 44.84},
    {name: "Cannes", lon: 7.0128, lat: 43.5513},
    {name: "Toulouse", lon: 1.444, lat: 43.6045},
    {name: "Reims", lon: 4.0347, lat: 49.2628}
  ];
var links = [
    {source:"Paris", target:"Lyon", distance:464},
    {source:"Paris", target:"Bordeaux", distance:582},
    {source:"Paris", target:"Reims", distance:144},
    {source:"Lyon", target:"Marseille", distance:314},
    {source:"Marseille", target:"Cannes", distance:175},
    {source:"Marseille", target:"Toulouse", distance:403},
    {source:"Bordeaux", target:"Toulouse", distance:245}
  ];

main(nodes, links);

function main(nodes, links) {
  links = setupNodesLinks(nodes, links);

  mapboxgl.accessToken = '<your access token here>';

  var map = new mapboxgl.Map({
    container: 'map', // container id
    style: "mapbox://styles/mapbox/light-v9",
    center: mapCenter,
    zoom: mapScale,  
  })

  map.addControl(new mapboxgl.NavigationControl());
  var container = map.getCanvasContainer()
  var svg = d3.select(container).append("svg")
 
  function markRoute(routePath) {
    links.forEach(function(l) {delete l.route;});
    routePath.forEach(function(i) {links[i.index]["route"]=true});
  }

  function midPoint(a,b) {
    var n=7;
    return [(a[0]*n+b[0])/(n+1),(a[1]*n+b[1])/(n+1)];
  }

  function mapboxProjection(lonlat) {
    var p = map.project(new mapboxgl.LngLat(lonlat[0], lonlat[1]))
    return [p.x, p.y];
  }

  function modName(name) {
    return name.replace(/\s/g,"_").replace(/\./g,"");
  }

  function lngLat2coord(lngLat) {
    return {coord:[lngLat.lng, lngLat.lat]};
  }

  function markNode(nodeName) {
    if (nodeName=="deselectAll") {d3.selectAll('circle').style("fill", defaultNodeColor);}
    else {
      var markNodeColor = 'blue';
      d3.select('circle#'+modName(nodeName)).style("fill", markNodeColor);
    }
  }

  svg.append('defs').append('marker')
      .attr({'id':'arrowhead',
             'viewBox':'0 -5 10 10',
             'refX':0,
             'refY':0,
             'orient':'auto',
             'markerWidth':10,
             'markerHeight':10,
             'markerUnits':'userSpaceOnUse',
             'xoverflow':'visible'})
      .append('svg:path')
      .attr('d', 'M 2,0 L 0,-3 L 10,0 L 0,3')
      .attr('fill', '#2080f0');

  var defaultWidth = 1, defaultLinkColor = "#a0e0a0";
  var link = svg.append("g").selectAll(".link")
      .data(links)
      .enter().append("path")
      .attr("class", "link")
      .style("stroke", defaultLinkColor)
      .style("stroke-width", defaultWidth);

  var defaultRadius = 3, defaultNodeColor = "#ccc";
  var node = svg.append("g").selectAll(".node")
      .data(nodes)
      .enter().append("circle")
      .attr("class", "node")
      .attr("r", defaultRadius)
      .attr("id", function(d) {return modName(d.name);})
      .style("fill", defaultNodeColor)
    
  link.each(function(d) {
      d.source.links.push(d);
      d.selection = d3.select(this);
  });

  node.each(function(d) {
      d.selection = d3.select(this);
  });

  node
      .append("title")
      .text(function(d) { return d.name });

  link.append("title")
      .text(function(d) { return d.source.name + " → " + d.target.name + "\n" + d.distance + " " + unitDistance});
  
  var query = {};

  map.on('click', function(e) {
    var q=lngLat2coord(e.lngLat);
    var nodeDistance=nodes.map(function(p) {return GeoDistance(p,q)});
    var imin = nodeDistance.indexOf(Math.min.apply(null,nodeDistance));    
    if (query.start==undefined) {
      query.start=nodes[imin].name;
      markNode("deselectAll");
    }
    else if (query.end==undefined) {
      query.end=nodes[imin].name;
      var result = astarRouting(nodes, links, query);
      markRoute(result.path);
      render();
      query = {};
    }
    markNode(nodes[imin].name);
  });


  function render() {
    node
      .each(function(d) {d.proj = mapboxProjection(d.coord); })
      .attr("transform", function(d) { return "translate(" + d.proj + ")" });
    link
      .attr("d", function(d) {var a=mapboxProjection(d.source.coord), c=mapboxProjection(d.target.coord), b=midPoint(a,c); return "M "+a+" L "+b+" L "+c;})
      .attr("marker-mid", function(d) {return (d.route===true)?'url(#arrowhead)':'none';})
  }

  map.on("viewreset", function() {
    render()
  })

  map.on("move", function() {
    render()
  })

  render()

}


function GeoDistance(p, q) {
  var x=p.coord[0]-q.coord[0], y=p.coord[1]-q.coord[1], t=p.coord[1]+q.coord[1];
  x*=Math.cos(t/2*DEGREE);
  return Math.hypot(x*x+y*y)*DEGREE*RE;
};


function setupNodesLinks(nodes, links) {

  function createReverseLinks(links) {
    return links.map(function(d) {
      return {"source":d.target, "target":d.source, "distance":d.distance}
    })
  }

  links = links.concat(createReverseLinks(links));

  var nodesByName = {};
  nodes.forEach(function(d) {
    d.coord = [+d.lon, +d.lat]
    nodesByName[d.name] = d;
    d.links = [];
  });

  links.forEach(function(d) {
    d.source = nodesByName[d.source]  // overwrite
    d.target = nodesByName[d.target]
    d.distance = +d.distance;
  });

  return links;
}


function astarRouting(nodes, links, query) {

  function GeoGraph(nodes, links) {
    this.nodes = {};
    this.links = links;
    for (var i=nodes.length-1; i>=0; i--) {
      var node = nodes[i];
      this.nodes[node.name] = new GeoNode(node);
    }
    this.init();
  }

  GeoGraph.prototype.init = function() {
    this.dirtyNodes = [];
    for (var k in this.nodes) {
      astar.cleanNode(this.nodes[k]);
    }
  };
  GeoGraph.prototype.cleanDirty = Graph.prototype.cleanDirty;
  GeoGraph.prototype.markDirty = Graph.prototype.markDirty;

  GeoGraph.prototype.neighbors = function(node) {
    var neighs=Object.keys(node.neighbors);
    if (!neighs.length) {
        neighs = createNeighbors(node, this.links);
    }
    return nodesByName(neighs, this.nodes);
  };

  function nodesByName(names, nodes) {
      return names.map(function(n) {return nodes[n];});
  }

  function createNeighbors(node, links) {
    var li, neighs = node.neighbors;
    for (var i=links.length-1; i>=0; i--) {
      if ((li = links[i]) && li.source.name==node.name) {
        neighs[li.target.name] = new Link(i, li.distance*units[unitDistance]);
      }
    }
    return Object.keys(neighs);
  };

  function Link(index, cost) {
    this.index = index;
    this.cost = cost;
  }

  function GeoNode(node) {
    this.name = node.name;
    this.coord = node.coord;
    this.neighbors = {};
  }

  GeoNode.prototype.weight = 1;
  GeoNode.prototype.isWall = function() {
    return this.weight === 0;
  };
  GeoNode.prototype.getCost = function(nodeSource) {
    return this.getNeighbor(nodeSource).cost;
  };

  GeoNode.prototype.getNeighbor = function(nodeSource) {
    return nodeSource.neighbors[this.name];
  }

  function getLink(node) {
    return node.getNeighbor(node.parent);
  }

  var graph = new GeoGraph(nodes, links);
  var startEnd = ["start", "end"].map(function(x) {return graph.nodes[query[x]];});
  var sTime = new Date();
  var result = astar.search(graph, startEnd[0], startEnd[1], {heuristic: GeoDistance});
  var deltaTime = new Date() - sTime;
  var route = [query["start"]].concat(result.map(function(x) {return x.name}));
  var path = result.map(function(x) {return getLink(x);});
  return {"route": route, "path": path, "calculationTime": deltaTime};
}

</script>
</body>
</html>
前回は地図表示に d3.mapzoom を利用しました。 ↩
なお Dijkstra アルゴリズムについては、"Putting Dijkstra's algorithm on the map (Simon Jacobs’s Block)" のコードがほぼ同様に動くと思います。 ↩