关于javascript:使用狄克斯特拉算法求地铁最少用时路径

2次阅读

共计 4987 个字符，预计需要花费 13 分钟才能阅读完成。

图”由节点和边组成。下面的地铁线路图中从“芍药居”登程到“太阳宫”须要 3 分种能够用下“图”示意。“图”中形容了“A”和“B”互为邻节点，其中 3 代表从节点“A”到“B”那条边的权重，边有权重的图称为“加权图”，不带权重的图称为“非加权图”。边上的剪头代表只能从 A 到 B 且须要的老本为 3，这种边代有方向的图称为“有向图”。

如果“A”能到“B”同时“B”也能够到”A”且老本同样为 3 则称为“无向图”

如果存在节“C”使得“A”到“B”，“B”能够到“C”，“C”又能够到“A”则称“A”、“B”、“C”为一个“环”。无向图中每一条边最可看为一个环。

狄克斯特拉算法的试用范畴

它用于计算加权图中的最短门路
只实用于有向无环图，（算法中会屏蔽环路）
不能将它用于蕴含负权边（边的权重为负值）的图

2. 算法流程

算法举例

有如下“有向加权图”，咱们要从“终点”登程到“起点”。

首先须要四个表，用于存储相干信息。

表一: 用于存储“图”信息“图”信息

表二：用于存储每结点从终点登程的最小老本，开始时只有“终点”老本为 0

表三：最小开销门路上每结点的父结点

表四：记录结点解决状态

算法流程如下：

1) 从表二及表四中找出最小开销的未解决节点，开始时只有“终点”

2) 从表一中看到从终点登程能够达到 A 和 B 开销别离为 5 和 3，更新表二

3) 更新表三记录以后达到 A、B 点的最小开销父结点为终点

4) 更新表四记录已解决过终点, 实现对一个节点的解决

5)（第二轮）从表二及表四中找出未解决过的最小开销的节点“B”（达到老本 3）

6) 从表一中看到从 B 登程能够达到节点 A 和起点开销别离为 1 和 4

因为从 B 到 A 的开销 1 加 B 的以后的最小达到开销 3 小于表二中 A 现有的最小开销 5 所以更新表二 A 的最小开销为 4 并更新表三中 A 节点的最小达到开销父节点为 B。
在表二中增加“起点”开销为 7（B 达到开销 3 加 B 到起点开销 4）
表三中增加起点父结点为 B

7) 记录 B 点已解决过

8)（第三轮）从表二及表四中找出未解决过的最小开销的节点“A”

9) 从点 A 出表可达到起点，点 A 以后最小达到老本为 4 加上 A 到起点的开销 1 小于表二中起点以后的最小开销，所以更新表二中起点的开销为 5 并更新表三中起点父节点为 A

10) 记录 A 点已解决

11) (第四轮) 从表二及表四中找出未解决过的最小开销的节点：“起点“

12) 因为起点无指向结点无需再解决，支接标记已解决实现起点

13) (第五轮)已无未解决结点实现操作

14) 最终后果

从表二中咱们晓得起点的最小达到开销为 5

从表三中咱们能够从起点的父结点一路推出最小开销门路为: 起点 < A < B < 终点

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 站

将狄克斯特拉算法利用于地铁图比照下面的例子有几个问题.

问题 1：地铁为一个无向图，如 A 能够到 B，B 也能够到 A，所以形容图信息时双向的图信息都要录入，如:

问题 2：图中第条边都是一个环，且如 A,B,C 也可组成一个环是否会对后果产生影响？

不会，因为算法中每次选出的解决节点都是达到老本最小的节点，只有从这个节登程到下一个节点老本更底时才会更新最小老本表和父节点表，且解决过的结点不会再次解决。

问题 3：如何解决换乘线路用时问题？

如：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

注：

狄克斯特拉算法局部次要参考算法图解

正文完