You need to enable JavaScript to run this app.
优惠活动
大模型
产品
解决方案
定价
更多

在多重图中应用Dijkstra算法的最优路径问题排查

avatar
开发者阿泽
2026-7-4
公交站点多重图上的Dijkstra算法优化问题

问题背景

在基于公交站点构建的多重图上应用Dijkstra算法时遇到两个核心问题：

  • 两站点间存在多条对应不同公交的边（如A到B可选公交1/2/3），算法能生成路径，但无法选择最优公交组合，导致路径非最优。
  • 存在名称相同但方向不同的站点（如示例中两个Praça dos Heróis站点，ID不同），当前逻辑对这类站点的步行成本处理不当。

图结构示例（JSON） 

{
  ...,
  "5382778889": {
    "name": "Praça dos Heróis",
    "coordinates": {
      "latitude": -25.9351311,
      "longitude": 32.5792925
    },
    "street": "Av. Acordos de Lusaka",
    "connections": [
      {
        "stop": 6797387579,
        "bus": 10046632,
        "path": [...]
      },
      {
        "stop": 6797387579,
        "bus": 10053951,
        "path": [...]
      },
      {
        "stop": 6797387579,
        "bus": 10053954,
        "path": [...]
      },
      {
        "stop": 6797387579,
        "bus": 10053956,
        "path": [...]
      },
      {
        "stop": 6797387579,
        "bus": 10070649,
        "path": [...]
      }
    ],
    "walking_connections": [
      {
        "stop": "5382778890"
      }
    ]
  },
  "5382778890": {
    "name": "Praça dos Heróis",
    "coordinates": {
      "latitude": -25.9351503,
      "longitude": 32.5794082
    },
    "street": "Av. Acordos de Lusaka",
    "connections": [
      {
        "stop": 5382778885,
        "bus": 10046631,
        "path": [...]
      },
      {
        "stop": 5382778885,
        "bus": 10053950,
        "path": [...]
      },
      {
        "stop": 5382778885,
        "bus": 10053955,
        "path": [...]
      },
      {
        "stop": 5382778885,
        "bus": 10070980,
        "path": [...]
      },
      {
        "stop": 5382778885,
        "bus": 10102978,
        "path": [...]
      }
    ],
    "walking_connections": [
      {
        "stop": "5382778889"
      }
    ]
  },
  ...
}

当前Dijkstra实现（JavaScript） 

findPaths(stops, startPoint, endPoint) {
  const distance = {};
  const queue = new PriorityQueue();
  const previous = {};
  const buses = {};
  const visited = new Set();

  for (const stop in stops) {
    distance[stop] = stop == startPoint ? 0 : Infinity;
    queue.enqueue(stop, distance[stop]);
  };
  
  while (!queue.isEmpty()) {
    const currentStop = Number(queue.dequeue());

    if (visited.has(currentStop)) {
      continue;
    };

    visited.add(currentStop);

    if (currentStop == endPoint) {
      const shortestPath = [];

      let stop = {
        stop: endPoint,
        name: stops[endPoint].name,
        coordinates: stops[endPoint].coordinates,
        street: stops[endPoint].street,
        path: [],
        bus: null,
      };

      while (stop) {
        shortestPath.unshift({...stop});
        stop = previous[stop.stop];
      };

      return shortestPath;
    };

    if (stops[currentStop] && stops[currentStop].connections) {
      for (const connection of stops[currentStop].connections) {
        const nextStop = connection.stop;
        const nextBus = connection.bus;
        const pathUsed = connection.path;

        let weight = 200;
        
        if (previous[currentStop] && previous[currentStop].bus) {
          if (nextBus == previous[currentStop].bus.id) {
            weight = 10;
          };
        };

        const newDistance = distance[currentStop] + weight;

        if (newDistance < distance[nextStop]) {
          distance[nextStop] = newDistance;

          previous[nextStop] = {
            stop: currentStop,
            name: stops[currentStop].name,
            coordinates: stops[currentStop].coordinates,
            street: stops[currentStop].street,
            path: pathUsed,
            bus: this.BusUseCase.getBusById(nextBus),
          };

          queue.enqueue(nextStop, newDistance);
        };
      };
    };

    if (stops[currentStop].walking_connections) {
      for (const connection of stops[currentStop].walking_connections) {
        const nextStop = connection.stop;
        const newDistance = distance[currentStop] + (stops[currentStop].name !== stops[nextStop].name ? 50 : 0);

        if (newDistance < distance[nextStop]) {
          distance[nextStop] = newDistance;
          previous[nextStop] = {
            stop: currentStop,
            name: stops[currentStop].name,
            coordinates: stops[currentStop].coordinates,
            street: stops[currentStop].street,
            path: [],
            bus: null,
          };

          queue.enqueue(nextStop, newDistance);
        };
      };
    };
  };

  return [];
};

问题根源分析

  1. 状态维度缺失：当前算法仅以站点ID作为状态标识，忽略了「当前乘坐的公交」这一关键维度。同一站点可能通过不同公交到达，后续换乘的成本差异极大，但当前实现会用一条路径覆盖其他路径，导致丢失更优的换乘可能性。
  2. 步行权重逻辑错误：同名不同ID的站点是反向站点，属于不同物理位置，步行需要成本，但当前代码中这类情况权重设为0，不符合实际场景，会干扰路径选择。

解决方案

1. 扩展算法状态维度

将Dijkstra的状态从单一站点ID扩展为(站点ID, 当前公交ID)的组合，确保每个站点下的不同公交换乘状态都被保留，不会被覆盖。具体调整：

  • distance对象改为存储${stopId}_${busId}形式的键，记录每个状态的累计距离；
  • 优先级队列中存储{ stopId, busId, distance }格式的元素；
  • previous对象同样以${stopId}_${busId}为键，记录每个状态的前驱信息。

2. 修正步行连接权重

将步行连接的权重改为固定值（如50），或根据站点坐标计算实际步行距离作为权重，避免同名反向站步行成本为0的错误逻辑。

3. 修改后的核心代码示例 

findPaths(stops, startPoint, endPoint) {
  // 状态键格式：`${stopId}_${busId}`，busId为null表示步行到达
  const distance = {};
  const queue = new PriorityQueue();
  const previous = {};
  const visited = new Set();

  // 初始化起点状态：无公交（步行/初始）
  const startKey = `${startPoint}_null`;
  distance[startKey] = 0;
  queue.enqueue({ stopId: Number(startPoint), busId: null }, 0);

  // 初始化所有其他状态为无穷大
  for (const stopId in stops) {
    const numStopId = Number(stopId);
    // 初始无公交状态
    const keyNull = `${numStopId}_null`;
    if (!distance[keyNull]) distance[keyNull] = Infinity;
    // 遍历所有可能的公交（从站点连接中提取）
    stops[stopId].connections?.forEach(conn => {
      const key = `${numStopId}_${conn.bus}`;
      if (!distance[key]) distance[key] = Infinity;
    });
  }

  while (!queue.isEmpty()) {
    const currentState = queue.dequeue();
    const currentStopId = currentState.stopId;
    const currentBusId = currentState.busId;
    const currentKey = `${currentStopId}_${currentBusId}`;

    if (visited.has(currentKey)) continue;
    visited.add(currentKey);

    // 到达终点时，收集所有到终点的状态，选距离最短的
    if (currentStopId === Number(endPoint)) {
      // 找到所有终点相关的状态，选距离最小的
      let minDist = Infinity;
      let bestKey = null;
      Object.keys(distance).forEach(key => {
        if (key.startsWith(`${endPoint}_`)) {
          if (distance[key] < minDist) {
            minDist = distance[key];
            bestKey = key;
          }
        }
      });

      // 回溯路径
      const shortestPath = [];
      let currentKey = bestKey;
      while (currentKey) {
        const [stopId, busId] = currentKey.split('_');
        const numStopId = Number(stopId);
        const bus = busId !== 'null' ? this.BusUseCase.getBusById(Number(busId)) : null;
        shortestPath.unshift({
          stop: numStopId,
          name: stops[numStopId].name,
          coordinates: stops[numStopId].coordinates,
          street: stops[numStopId].street,
          bus: bus
        });
        currentKey = previous[currentKey];
      }
      return shortestPath;
    }

    // 处理公交连接
    if (stops[currentStopId]?.connections) {
      for (const conn of stops[currentStopId].connections) {
        const nextStopId = conn.stop;
        const nextBusId = conn.bus;
        const nextKey = `${nextStopId}_${nextBusId}`;

        // 计算权重：同公交续乘权重10，换乘权重200
        let weight = 200;
        if (currentBusId === nextBusId) {
          weight = 10;
        }

        const newDistance = distance[currentKey] + weight;
        if (newDistance < distance[nextKey]) {
          distance[nextKey] = newDistance;
          previous[nextKey] = currentKey;
          queue.enqueue({ stopId: nextStopId, busId: nextBusId }, newDistance);
        }
      }
    }

    // 处理步行连接
    if (stops[currentStopId]?.walking_connections) {
      for (const walkConn of stops[currentStopId].walking_connections) {
        const nextStopId = Number(walkConn.stop);
        const nextKey = `${nextStopId}_null`; // 步行后无当前公交

        // 步行固定权重50，或根据坐标计算实际距离
        const weight = 50;
        const newDistance = distance[currentKey] + weight;

        if (newDistance < distance[nextKey]) {
          distance[nextKey] = newDistance;
          previous[nextKey] = currentKey;
          queue.enqueue({ stopId: nextStopId, busId: null }, newDistance);
        }
      }
    }
  }

  return [];
}

关键优化点说明

  • 状态扩展后，同一站点下的不同公交换乘路径都被保留，算法能在所有可能的状态中选择最优路径；
  • 步行权重修正为固定值，避免反向站无成本步行的错误；
  • 终点判断时遍历所有到达终点的状态，确保选出距离最短的路径。

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

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级，最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分)， 限时 9.9 元起

产品介绍相关文档
相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级，最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分)， 限时 9.9 元起

产品介绍相关文档
火山引擎 最新活动
全面开放
Doubao-Seedance-2.5全新模型升级

模型再升级,30秒超长叙事, 模态参考扩容

HOT
方舟Codingplan

模型自由，工具不限，最新支持 Deepseek-V4 系列、GLM-5.3 系列

HOT
方舟Agent plan

超全模态模型 × Harness 升级，最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列

HOT
新用户特惠专场

大模型19元起，Al应用9.9元畅享，新人首购爆款尽享优惠

最近更新时间：2026.07.04 21:14:55