Dijkstra算法找到最短的地铁路线

什么是“图”

图“由节点和边组成。在上面的地铁地图中，从“芍药居”宫出发”如果需要3分钟，可以用下面的“图”来表示。 “图”定义“A”和“B”是相邻节点，其中3表示节点“A”到“B”的边的权重，该边是带权图称为“带权图”，未加权的图称为“未加权图”。 B，价格为3。这种边代表有向图，称为“有向图”。 3 成本也，称为“无向图”

如果有一个节点“C”导致“A”走到“B”，“B”可以走到“C”，“C”也可以。走到“A”，则“A”、“B”、“C”称为“环”。 （算法被阻止） 不能用于有负边的图（负边权重）

2。算法流程

1. 算法示例

有如下“阶次加权图”，它必须从“起点”到“终点”。

首先需要四张表来存储相关信息。

表1：用于存储有关“图”的信息

表2：用于存储每个节点从起点开始的最小成本。一开始，只有“起始”成本为 0

表 3：成本最小时各节点的父节点

表 4：节点处理状态记录

算法的流程如下：

1）在表2和表4中找到成本最低的未处理节点，一开始只有“上一个”

2）从表1可以看出，从表1到达A和B的成本起点分别为 5 和 3。更新表2

3）更新表3，记录到达A点和B点的最小成本。记录已处理的起点，完成节点

的处理5）（旋转第二）求未处理的最小成本表2和表4 节点“B”（到达成本3）

6）从表1中，我们看到节点A的1和4成本以及从B可以获得的端点

• 因为来自B的成本A 的成本是 1 加 B 的当前成本。表2、5中A的最低价格，所以表2中A的续费最低价格为4，表3中节点A到达的续费价格。父节点为B。
• 将表2中“终点”的成本添加到7（到达成本B 3加上终点成本4中的B）
• 将父节点添加到B

7 -表3的母亲）记录这一点 B.已处理的

8）（第三轮）在表2和表4中找到未处理的最低成本节点“A”

9）最后一个点是从表外的A点得到的，也是当前最小的。到达点 A 的成本为 4 加上从 A 到终点的成本 1 小于表 2 中终点的当前最小成本，因此更新表 2 中端点的成本为 5，父节点表3中端点的节点更新为A

10) 记录有A点被处理 2 最终点的处理

13) (第五轮) 没有未处理的节点完成操作

14) 最终结果

从表2中我们知道，到达点3的最小成本为5

从表3中我们可以得出从父节点到终点的最短路径：终点 4。代码实现（TypeScript）

/** * 狄克斯特拉查找结果 */
export interface DijkstraFindResult<T_node> {      
  /** 差找的图 */      
  graph: Map<T_node, Map<T_node, number>>;      
  /** 开始节点 */      
  startNode: T_node;      
  /** 结束节点 */      
  endNode: T_node;      
  /** 是否找到 */      
  isFind: boolean;      
  /** 最小成本路径节点链*/      
  parents: Map<T_node, T_node>;      
  /** 结果路径 */      
  path: T_node[];      
  /** 每节点最小到达成本 */      
  arriveCosts: Map<T_node, number>;
}

/** 
* 查找未处理过的最小成本节点 
* @param costs key:节点信息， value:当前到达成本 
* @param processed key:节点信息 value: 是否已处理过 
*/
function findMinCostNode<T_node>(  costs: Map<T_node, number>,  processed: Map<T_node, boolean>): T_node | null {  
  var minCost: number = Number.MAX_VALUE;  
  var minCostNode: T_node | null = null;  
  for (const [node, cost] of costs) {    
      if (cost < minCost && !processed.get(node)) {      
          minCost = cost;      
          minCostNode = node;    
      }  
  }  
  return minCostNode;
}
/** 
* 返回从开始节点到结束节点路径 
* @param endNode 结束节点 
* @param parents key:节点A  value:节点A父节点 
*/
function getPath<T_node>(  endNode: T_node,  parents: Map<T_node, T_node>): T_node[] {  
  let path = [endNode];  
  let nParent = parents.get(endNode);  
  while (nParent) {    
      path.push(nParent);    
      nParent = parents.get(nParent);  
  }  
  path.reverse();  
  return path;
}




/** 
* 狄克斯特拉查找(找出成本最短路径) 
* - 用于加权(无负权边)有向图无环图 
* @param graph 要查找的"图", Map<节点 ,Map<相邻节点，到达成本>> 
* @param startNode 开始节点 
* @param endNode 结束节点 
*/
export function dijkstraFind<T_node>(  
  graph: Map<T_node, Map<T_node, number>>,  
  startNode: T_node,  
  endNode: T_node): DijkstraFindResult<T_node> {  
  /** 到节点最小成本 * k:节点 * v:从出发点到节点最小成本 */  
  let arriveCosts: Map<T_node, number> = new Map();  
  /** 最小成本路径父节点 k:节点A v: 节点A在最小成本路径上的父节点 */  
  let parents: Map<T_node, T_node> = new Map();  
  /** 已处理节点  k: 节点  v: 是否已处理过 */  
  let processedNode: Map<T_node, boolean> = new Map();  
  // 设置起点成本为零  
  arriveCosts.set(startNode, 0);  
  // 当前节点  
  let currentNode: T_node | null = startNode;  
  // 当前节点到达成本  
  let currentNodeCost: number = 0;  
  // 当前节点邻节点  
  let neighbors: Map<T_node, number>;  
  let isFind: boolean = false;  
  while (currentNode) {    
      // 标记是否找到目标结点    
     if (currentNode === endNode) isFind = true;    
     // 这里costs中一定会有node对映值所以强制转型成number    
     currentNodeCost = <number>arriveCosts.get(currentNode);    
     neighbors = graph.get(currentNode) || new Map();    
     //遍历邻节点更新最小成本    
     for (const [neighborNode, neighborCost] of neighbors) {      
         // 邻节点之前算出的最小到达成本      
         let tmpPrevMinCost = arriveCosts.get(neighborNode);      
         let prevCost: number =  tmpPrevMinCost === undefined ? Number.MAX_VALUE : tmpPrevMinCost;      
         // 邻节点经过当前节点的成本      
         let newCost = currentNodeCost + neighborCost;      
         // 如果经当前结点成本更小，更新成本记录及邻节点最小成本路径父结点      
         if (newCost < prevCost) {        
             arriveCosts.set(neighborNode, newCost);        
             parents.set(neighborNode, <T_node>currentNode);      
         }    
     }    
     // 记录已处理结点    
     processedNode.set(<T_node>currentNode, true);    
     // 找出下一个未处理的可到达最小成本结点    
     currentNode = findMinCostNode(arriveCosts, processedNode);  
 }  
 // 从起始点到终点路径  
 let path: T_node[] = [];  
 if (isFind) {    
     path = getPath(endNode, parents);  
 }  
 return {    
     isFind: isFind,    
     path: path,    
     graph: graph,    
     arriveCosts: arriveCosts,    
     parents: parents,    
     startNode: startNode,    
     endNode,  
 };
} //eof dijkstraFind


// 测试

function objToMap(obj: any): Map<string, number> {  
  let map: Map<string, number> = new Map();  
  for (let k in obj) {    
      map.set(k, obj[k]);  
  }  
  return map;
}

/** 图 */
const graph: Map<string, Map<string, number>> = new Map();
graph.set("start", objToMap({ a: 5, b: 3 }));
graph.set("a", objToMap({ end: 1 }));
graph.set("b", objToMap({ a: 1, end: 4 }));
graph.set("end", new Map());

let result = dijkstraFind(graph, "start", "end");
console.log(result);

// 输出
/*
{  
  isFind: true,  
  path: [ 'start', 'b', 'a', 'end' ],  
  graph: Map {    
      'start' => Map { 'a' => 5, 'b' => 3 },    
      'a' => Map { 'start' => 5, 'end' => 1, 'b' => 1 },    
      'b' => Map { 'start' => 3, 'end' => 4, 'a' => 1 },    
      'end' => Map { 'a' => 1, 'b' => 4 }  
  },  
  arriveCosts: Map { 
      'start' => 0, 
      'a' => 4, 
      'b' => 3, 
      'end' => 5 
  },  
  parents: Map { 
      'a' => 'b', 
      'b' => 'start', 
      'end' => 'a' 
  },  
  startNode: 'start',  
  endNode: 'end'
}

*/

查找两个车站之间的最新时间线

以上面的例子为例，其中的“图”被视为地铁地图：这就是我们希望人们从 A 站到 D 站的路线

与上面的例子相比，将 Dijkstra 算法应用到地铁地图上存在很多问题。

问题1：一部没有地铁运行的电影。例如A可以到B，B可以到A。因此，在指定图信息时，必须包含图信息的两条路径，如：

问题2：图的第三条边是a循环。 ，如果A、B、C也能组成环，会影响结果吗？

否，因为算法中选择的每个处理节点都是到达成本最小的节点，当从该节点到下一个节点的成本较低时，最小表和父节点表都会被更新，并且经过的处理节点将不再被处理。

问题三：线路位移问题如何处理？

例：1号线换乘5号线需要2分钟，5号线换乘2号线需要1分钟。

从上图可以看出，尤其是从A到D换乘，最短路线不考虑：

A > B > C > D

如果算上行程时间，最短路线为：

A > C > D

那怎么处理呢？我们可以将车站内的换乘路线作为局部图，粘贴到地铁地图上，如：

上图中，节点 B 被替换为三个节点 B_A、B_D、B_C。这意味着B_A到B_C和B_D到B_C的权重相同（或不同），这意味着从第1行转移到第5行需要2分钟。B_A到B_D的值为0，这意味着。但不需要从A经B换乘到D。使用上图作为新算法的输入数据，可以根据换乘时间计算出最便宜的路线。

参考：

《算法图解》【美国】Aditya Dhargava

注：

Dijkstra 的算法部分主要参考算法图