algorithm - 我如何制作边缘系统以便我可以实现 Dijkstra 或 A* 算法？

Question

我想在 geoJson 文件提供的功能列表上应用 Dijkstra 算法，我有多达 100 个功能查看示例。 到目前为止我做了什么:

1. 从特征中提取所有点(称为点的变量)

2。我已经使用 points 的索引构建了一个这样的邻接表所以 0-1-10 将是索引 0 在 points 的点，对于 1 也是如此，第三个是彼此之间的距离。 3. 我已经建立了邻接数组，但我没有看到它有任何用处图像中显示的示例不是完整的功能，我只是在寻找起点，然后我可以处理 map 的其余部分。

1. 所有黑点都是(lat , lang)

我如何制作边缘系统以便我可以实现 Dijkstra 或 A* 算法

我的问题是如何继续从 A 到 B？ 欢迎提出任何建议。

edit 1 : added code

edit 2 : updated question

	var start = [34.000750, 71.485753];
            var end = [34.000937, 71.485180];
           
           	var points=[];
           	var nodes=[];
           	var features=[];
           	var adjacent=[];

           	var map = L.map('map').setView(start, 17);;

	       map.attributionControl.addAttribution('<a href="https://github.com/tomchadwin/qgis2web" target="_blank">qgis2web</a>');
        var bounds_group = new L.featureGroup([]);
        var basemap0 = L.tileLayer('http://{s}.tile.openstreetmap.org/{z}/{x}/{y}.png', {
            attribution: '&copy; <a href="http://openstreetmap.org">OpenStreetMap</a> contributors,<a href="http://creativecommons.org/licenses/by-sa/2.0/">CC-BY-SA</a>',
            maxZoom: 22
        });
        basemap0.addTo(map);
        L.geoJSON(data).addTo(map);
	       //OpenStreetMap_BlackAndWhite.addTo(map)
 	        //basemap0.addTo(map);
           	function getid(){
           		var possible = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";
           		var d = possible.charAt(Math.floor(Math.random() * possible.length));
           		while(nodes.indexOf(d) >-1){
           			 d = possible.charAt(Math.floor(Math.random() * possible.length));
           		}
        		return d;
           	}
            L.geoJSON(data, {
                onEachFeature: function(feature, layer) {
                    //console.log(feature);
                    points.push.apply(points,feature.geometry.coordinates);
                    features.push(feature.geometry.coordinates);
                   // return L.Polyline(layer, geojsonMarkerOptions);
                }
            });

            function init(){
            	var marks= [];
	            for (var i = 0; i < features.length; i++) {
	                var s = features[i];

	                //var m = L.marker([s[1],s[0]]);
	                //marks.push(m);
	                for (var j = 0; j < s.length; j++) {
	                    var k = s[j];

	                    var m = L.marker([k[1],k[0]]);
	                    m.on('click',function(e){
	                        console.log(this.getLatLng());
	                    })
	                    marks.push(m);
	                }
	               
	            }
	            var heuristik
	            for (var i = 0; i < marks.length-1; i++) {
	                var lt = marks[i].getLatLng().distanceTo(marks[i+1].getLatLng());
	                var a =i;
	                var b =i+1;
	                if(lt != 0 ){
	                console.log(a,b,lt,);

	                adjacent.push([a,b,lt]);
	                }
	                //Array.prototype.push.apply(adjacent,{a,b,lt});
	     
	            }
	            //console.log(adjacent)
            }

html,body {
		width: 100%;
		height: 100%;
		overflow: hidden;
	}
	#map{
		width: 100%;
		height: 100%;
	}	

<link rel="stylesheet" href="https://unpkg.com/leaflet@1.0.3/dist/leaflet.css" />
<script src="https://unpkg.com/leaflet@1.0.3/dist/leaflet.js"></script>
 <script src="https://raw.githubusercontent.com/andrewhayward/dijkstra/master/graph.js"></script>
 
 		<script></script>
		<script>
    var data = {
"type": "FeatureCollection",
"crs": { "type": "name", "properties": { "name": "urn:ogc:def:crs:OGC:1.3:CRS84" } },
"features": [
{ "type": "Feature", "properties": { "Place": "Kmc Road" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.484445376090477, 34.000556224204104 ], [ 71.484619381903997, 34.00055622349123 ], [ 71.485795423886529, 34.000556218673154 ], [ 71.486389444907786, 34.000556088482497 ] ] } },
{ "type": "Feature", "properties": { "Place": "UET Main Road" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.486384748456004, 34.002041741407623 ], [ 71.485121131034504, 34.002036564553677 ], [ 71.484897906943033, 34.002035650037541 ], [ 71.484080666224514, 34.002032301923023 ] ] } },
{ "type": "Feature", "properties": { "Place": "Road 2" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.486389444907786, 34.000556088482497 ], [ 71.486384748456004, 34.002041741407623 ], [ 71.48638137935751, 34.003043552173651 ], [ 71.486380078137188, 34.003430473641167 ], [ 71.486380045906941, 34.003440057392226 ] ] } },
{ "type": "Feature", "properties": { "Place": "Hostel Road" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.486380078137188, 34.003430473641167 ], [ 71.484890807505366, 34.00343866205165 ], [ 71.483730352446614, 34.003445042545671 ] ] } },
{ "type": "Feature", "properties": { "Place": "Commerce College Road" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.483730352446614, 34.003445042545671 ], [ 71.483792886191907, 34.003192857311085 ], [ 71.484080666224514, 34.002032301923023 ], [ 71.484445376090477, 34.000556224204104 ] ] } },
{ "type": "Feature", "properties": { "Place": "Civil Engineering" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.485795429415916, 34.000635421476822 ], [ 71.485793037373725, 34.000750625722446 ], [ 71.485761836269248, 34.000750627900693 ] ] } },
{ "type": "Feature", "properties": { "Place": "Structure Labs & Library" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.485793037373725, 34.000750625722446 ], [ 71.485824238478202, 34.000750623544199 ] ] } },
{ "type": "Feature", "properties": { "Place": "Concrete Testing Lab" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.485793037373725, 34.000750625722446 ], [ 71.485797844581057, 34.000851428955635 ], [ 71.485838646025371, 34.000851426107154 ], [ 71.485841053985538, 34.000964229932706 ] ] } },
{ "type": "Feature", "properties": { "Place": "Hydraulic Lab" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.485797844581057, 34.000851428955635 ], [ 71.485800253043891, 34.000971433036057 ], [ 71.485783452449184, 34.000971434208964 ], [ 71.485785871468138, 34.001242643641845 ], [ 71.485809872317731, 34.001242641966272 ] ] } },
{ "type": "Feature", "properties": { "Place": "Civil Parking" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.485795429415916, 34.000635421476822 ], [ 71.485529019817847, 34.000633039990753 ] ] } },
{ "type": "Feature", "properties": { "Place": "CS & IT" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.485797844581057, 34.000851428955635 ], [ 71.485181022746431, 34.000851472017921 ], [ 71.485181028778499, 34.000937875076467 ] ] } },
{ "type": "Feature", "properties": { "Place": "Earthquake Center" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.485181022746431, 34.000851472017921 ], [ 71.485181021908645, 34.000839471593132 ], [ 71.485181018725044, 34.000793869978892 ], [ 71.485046613967313, 34.000793879362114 ] ] } },
{ "type": "Feature", "properties": { "Place": "New Earthquake Center" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.485181021908645, 34.000839471593132 ], [ 71.484837809926972, 34.000841895638814 ], [ 71.484837796857477, 34.000654689011959 ], [ 71.484837795852144, 34.000640288502204 ], [ 71.484621788205772, 34.000640303582379 ] ] } },
{ "type": "Feature", "properties": { "Place": "Girls Common Room" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.485181028778499, 34.000937875076467 ], [ 71.485181035313246, 34.001031478389898 ], [ 71.485181040507527, 34.001105881023648 ] ] } },
{ "type": "Feature", "properties": { "Place": "Mechanical Engineering" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.485181040507527, 34.001105881023648 ], [ 71.485181063088987, 34.001429336832032 ] ] } },
{ "type": "Feature", "properties": { "Place": "New Earthquake Gate" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.484621788205772, 34.000640303582379 ], [ 71.484619381903997, 34.00055622349123 ] ] } },
{ "type": "Feature", "properties": { "Place": "Civil Main Gate" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.485795429415916, 34.000635421476822 ], [ 71.485795423886529, 34.000556218673154 ] ] } },
{ "type": "Feature", "properties": { "Place": "New Academic Block" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.485181063088987, 34.001429336832032 ], [ 71.485125861392447, 34.001433029533452 ], [ 71.485128269185054, 34.001543433274037 ], [ 71.48599229960297, 34.001540972868369 ], [ 71.485982728920817, 34.001965788576456 ], [ 71.485677917963386, 34.001963409771299 ], [ 71.485663520302097, 34.00200421222096 ], [ 71.485557916396317, 34.002001819508536 ], [ 71.485567513887673, 34.001961017393988 ], [ 71.485118698167781, 34.001963448812212 ], [ 71.485125876678964, 34.001651992925943 ], [ 71.485128269352614, 34.001545833359003 ] ] } },
{ "type": "Feature", "properties": { "Place": "Tennis Lawn" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.485181035313246, 34.001031478389898 ], [ 71.484926626229907, 34.001030384828667 ], [ 71.484926669794874, 34.001654406918178 ], [ 71.485125876678964, 34.001651992925943 ] ] } },
{ "type": "Feature", "properties": { "Place": "Agriculture Engineering" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.484897906943033, 34.002035650037541 ], [ 71.484890084806153, 34.002365054141571 ], [ 71.484888323226841, 34.002439237380912 ] ] } },
{ "type": "Feature", "properties": { "Place": "Chemical & Industrial Egineering" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.484888323226841, 34.002439237380912 ], [ 71.484883546063472, 34.002768782456975 ] ] } },
{ "type": "Feature", "properties": { "Place": "Main Gate Entrance" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.485118698167781, 34.001963448812212 ], [ 71.485121131034504, 34.002036564553677 ] ] } },
{ "type": "Feature", "properties": { "Place": "Computer System Parking" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.484883546063472, 34.002768782456975 ], [ 71.484888363916895, 34.003022079805255 ], [ 71.484600352381278, 34.003002899232484 ] ] } },
{ "type": "Feature", "properties": { "Place": "Computer System Engineering" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.484888363916895, 34.003022079805255 ], [ 71.484888365089802, 34.003038880399977 ], [ 71.48488837681883, 34.003206886347151 ] ] } },
{ "type": "Feature", "properties": { "Place": "Hostel Road Entrance" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.48488837681883, 34.003206886347151 ], [ 71.484888930241823, 34.003259657448353 ], [ 71.484890807505366, 34.00343866205165 ] ] } },
{ "type": "Feature", "properties": { "Place": "Canteen" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.484888930241823, 34.003259657448353 ], [ 71.485097187393905, 34.003252473383881 ] ] } },
{ "type": "Feature", "properties": { "Place": "High Tension Lab" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.484888365089802, 34.003038880399977 ], [ 71.485572389638421, 34.003043632815995 ] ] } },
{ "type": "Feature", "properties": { "Place": "New Admin Block (CMS)" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.485572389638421, 34.003043632815995 ], [ 71.485975604079186, 34.00304600475129 ] ] } },
{ "type": "Feature", "properties": { "Place": "Road 2 Gate" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.485975604079186, 34.00304600475129 ], [ 71.486088447014453, 34.003045322708608 ], [ 71.48638137935751, 34.003043552173651 ] ] } },
{ "type": "Feature", "properties": { "Place": "VC Lawn" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.486088447014453, 34.003045322708608 ], [ 71.486085990058683, 34.002789187952963 ] ] } },
{ "type": "Feature", "properties": { "Place": "Electrical Engineering" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.485572389638421, 34.003043632815995 ], [ 71.485569981549489, 34.002928984566658 ] ] } },
{ "type": "Feature", "properties": { "Place": "Provost Office" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.486085990058683, 34.002789187952963 ], [ 71.486090753237178, 34.00225932450293 ], [ 71.485711539310884, 34.002252150722143 ], [ 71.485469132237981, 34.002273768410092 ], [ 71.485303533078067, 34.00236978336995 ], [ 71.485121126788684, 34.002372196189278 ] ] } },
{ "type": "Feature", "properties": { "Place": "Electrical Lawn" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.485121126788684, 34.002372196189278 ], [ 71.484890084806153, 34.002365054141571 ] ] } },
{ "type": "Feature", "properties": { "Place": "Director of Works" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.483792886191907, 34.003192857311085 ], [ 71.483894742186976, 34.003214711632012 ] ] } }
]
}

    </script>
 
 
	 
	<div id="map">
		
	</div>
	 
 
 

Answer 1

你的问题太宽泛了。您没有指定平台(您要在 Web 浏览器中计算最短路径吗？在 JS 后端？在带有 GeoJSON 列的 PostGIS DB 表中？)，这让我们猜测。请注意，“传单功能”不添加任何信息，因为传单也可以从不同的数据源加载数据，并且不保证您将在前端计算最短路径。

已经有数百路径寻找算法的实现，所以:

• 对于网络浏览器，我会选择 Per Liedman 的 https://github.com/perliedman/geojson-path-finder ，它实现了普通的旧 Dijkstra
• 对于后端服务，我会选择 OSRM https://github.com/Project-OSRM/osrm-backend及其精彩边缘收缩算法。
• 对于数据存储级别的路由计算，pgRouting http://pgrouting.org/是显而易见的选择之一。十二种不同的算法？是的，请。