什么是“图”
图”由节点和边组成。下面的地铁线路图中从“芍药居”登程到“太阳宫”须要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
注：
狄克斯特拉算法局部次要参考算法图解
发表回复