如何在Mapbox/Leaflet中实现Dijkstra算法用于校园自定义道路寻路？

Leaflet 实现步骤 #

1. 构建自定义道路的图结构 #

先把校园道路抽象成节点-边的图模型：

• 节点：道路交叉口、拐点的经纬度坐标，给每个节点分配唯一ID
• 边：连接两个节点的路段，记录起点/终点ID，以及路段权重（比如实际长度，用两点距离公式计算）

示例数据结构：

// 节点：ID -> [纬度, 经度]
const nodes = {
  1: [39.9042, 116.4074],
  2: [39.9050, 116.4080],
  3: [39.9035, 116.4090],
  // ... 补充更多校园节点
};

// 边：起点ID、终点ID、权重（距离，单位：米）
const edges = [
  { from: 1, to: 2, weight: 80 },
  { from: 2, to: 3, weight: 120 },
  { from: 1, to: 3, weight: 180 },
  // ... 补充更多道路连接
];

2. 实现Dijkstra算法核心 #

写一个独立的算法函数，输入起点ID、终点ID和图结构，返回最短路径的节点序列：

function dijkstra(startId, endId, nodes, edges) {
  // 初始化距离表：key为节点ID，value为到起点的最短距离
  const distances = {};
  // 记录路径前驱节点
  const previous = {};
  // 未访问节点集合
  const unvisited = new Set(Object.keys(nodes));

  // 初始化所有节点距离为无穷大，起点距离设为0
  Object.keys(nodes).forEach(id => {
    distances[id] = Infinity;
  });
  distances[startId] = 0;

  while (unvisited.size > 0) {
    // 找到未访问节点中距离最小的节点
    let currentId = Array.from(unvisited).reduce((minId, id) => {
      return distances[id] < distances[minId] ? id : minId;
    });

    if (currentId === endId) break; // 到达终点，提前退出循环

    unvisited.delete(currentId);

    // 遍历所有与当前节点相连的边
    edges.forEach(edge => {
      let neighborId, weight;
      if (edge.from === currentId) {
        neighborId = edge.to;
        weight = edge.weight;
      } else if (edge.to === currentId) {
        neighborId = edge.from;
        weight = edge.weight; // 双向道路权重一致
      } else {
        return;
      }

      if (!unvisited.has(neighborId)) return;

      const newDistance = distances[currentId] + weight;
      if (newDistance < distances[neighborId]) {
        distances[neighborId] = newDistance;
        previous[neighborId] = currentId;
      }
    });
  }

  // 回溯生成完整路径
  const path = [];
  let current = endId;
  while (current) {
    path.unshift(current);
    current = previous[current];
  }

  // 若起点到终点不可达，返回空数组
  return path.length > 0 && path[0] === startId ? path : [];
}

3. 在Leaflet中渲染路径 #

把算法返回的节点ID序列转换成经纬度数组，用L.polyline绘制：

// 假设已初始化Leaflet地图：const map = L.map('map').setView([39.9042, 116.4074], 16);

// 获取最短路径的节点ID数组
const shortestPathIds = dijkstra('1', '3', nodes, edges);
// 转换为经纬度数组
const pathCoords = shortestPathIds.map(id => nodes[id]);

// 绘制红色路径
L.polyline(pathCoords, { color: 'red', weight: 4 }).addTo(map);

Mapbox 实现步骤 #

Mapbox官方Directions API无法直接适配自定义道路，核心思路和Leaflet一致：自行构建图结构+实现Dijkstra，再用Mapbox GL JS渲染路径。

1. 加载自定义道路数据（可选） #

把校园道路的GeoJSON加载到Mapbox地图上，作为道路背景：

// 假设已初始化Mapbox地图：mapboxgl.accessToken = '你的token'; const map = new mapboxgl.Map({...});

map.addSource('campus-roads', {
  type: 'geojson',
  data: '你的校园道路GeoJSON路径' // 也可直接传入GeoJSON对象
});

map.addLayer({
  id: 'campus-roads-layer',
  type: 'line',
  source: 'campus-roads',
  paint: { 'line-color': '#888', 'line-width': 3 }
});

2. 复用Dijkstra算法 #

直接使用Leaflet部分的dijkstra函数，注意Mapbox坐标格式为**[经度, 纬度]**，和Leaflet的[纬度, 经度]区分开，调整nodes的存储格式即可。

3. 在Mapbox中渲染路径 #

把路径坐标转换成Mapbox支持的GeoJSON格式，添加为图层：

const shortestPathIds = dijkstra('1', '3', nodes, edges);
// 转换为Mapbox要求的[经度, 纬度]格式
const pathCoords = shortestPathIds.map(id => [nodes[id][1], nodes[id][0]]);

// 添加路径数据源
map.addSource('shortest-path', {
  type: 'geojson',
  data: {
    type: 'Feature',
    geometry: {
      type: 'LineString',
      coordinates: pathCoords
    }
  }
});

// 添加路径图层
map.addLayer({
  id: 'shortest-path-layer',
  type: 'line',
  source: 'shortest-path',
  paint: { 'line-color': '#ff0000', 'line-width': 4, 'line-opacity': 0.8 }
});

关键注意事项 #

• 节点生成：如果校园道路是GeoJSON线串，可借助Turf.js的turf.getCoords提取所有拐点作为节点，再自动生成相邻拐点间的边
• 权重计算：若需要精准权重，不要用直线距离，而是用道路实际长度（可通过Turf.js的turf.length计算GeoJSON线串长度）
• 性能优化：当节点数量较多时，建议用高效优先队列（如heap-js库）代替数组遍历寻找最小距离节点

内容的提问来源于stack exchange，提问作者NoobMaster69