上面图中我们可以使用广度优先搜索查找到从双子峰到金门大桥的最短路径，但这个最短路径只是因为段数最少-只有三段，但不一定是最快路径。如果给这些路段加上时间，你将会发现有更快的路径。
像上面这样有时间标注的图中，我们要找出最快的路径，该如何办？这时候我们就可以使用-狄克斯特拉算法。
1. 使用
上面的每个数字表示的都是时间，单位分钟。如果使用广度优先搜索，将得到下面这条段数最少的路径。
这条路径耗时7分钟。如果用狄克斯特拉算法需要以下四个步骤：
1). 找出“最便宜”的节点，即可在最短时间内到达的节点。
2). 更新该节点的邻居的开销
3). 重复这个过程，直到对图中的每个节点都这样做了。
4). 计算最终路径。
以上面的案例为例
-
第一步：找出最便宜的节点。
我们从起点可以直接到达 A 节点或者 B 节点，前往 A 节点需要6分钟，前往 B 节点需要2分钟。其他的节点，我们还不知道具体需要多长时间。
由于我们还不知道前往终点需要多长时间，所以我们假设为无穷大。所以我们前往节点 B 是最近的-2分钟就能到达
- 第二步：计算经节点 B 前往其各个邻居节点所需的时间。
从起点经 B 节点到 A 节点需要 5 分钟，对于节点 B ，你找到了
1). 前往节点 A 的更短路径（时间从6分钟缩短到了5分钟）
2). 前往终点的最短路径（时间从无穷大缩短到7分钟）
- 第三步：重复！
重复第一步：找出可在最短时间内前往的节点。你对节点 B 执行了第二步，除节点 B 外，可在最短时间内前往的节点是 A
重复第二步：更新节点 A 的所有邻居开销
你发现前往终点的时间为 6 分钟！
对每个节点都运行狄克斯特拉算法（不包括终点），现在，我们可以知道：
1). 前往节点 B 需要2分钟
2). 前往节点 A 需要5分钟
3). 前往终点需要6分钟
2. 场景
狄克斯特拉算法用于每条边都有关联数字的图，这些数字称为权重。
带权重的图称为加权图，不带权重的图称为非加权图
对于非加权图的最短路径，使用广度优先搜索。加权图的最短路径使用狄克斯特拉算法，并且只适用于有向无环图
3. 实现
我们需要用到三个散列表
随着算法的进行，我们需要不断更新散列表 costs 和 parents。首先我们需要先实现这个图，我们可以使用一个散列表，这里需要我们同时存储邻居和前往邻居的开销。例如，起点有两个邻居 A 和 B
如何表示这些边的权重那？我们可以继续使用另一个散列表
const graph = {};
graph["start"] = {};
graph["start"]["a"] = 6;
graph["start"]["b"] = 2;
我们继续添加其他节点及其邻居
graph["a"] = {};
graph["a"]["fin"] = 1;
graph["b"] = {};
graph["b"]["a"] = 3;
graph["b"]["fin"] = 5;
graph["fin"] = {};
整个图的散列表类似于下面
接下来，需要用一个散列表来存储每个节点的开销。
节点的开销指的是从起点出发前往该节点需要多长时间。我们知道，从起点到节点 B 需要2分钟，从起点到节点 A 需要6分钟（但我们可能会找到所需时间更短的路径）。我们不知道到终点需要多长时间。对于还不知道的开销，我们可以将其设置为无穷大
const costs = {};
costs["a"] = 6;
costs["b"] = 2;
costs["fin"] = Infinity;
还需要一个存储父节点的散列表：
const parents = {};
parents["a"] = "start";
parents["b"] = "start";
parents["fin"] = undefined;
最后，我们需要一个数组，用于记录处理过的节点，因为对于同一个节点我们不需要多次处理
const processed = [];
具体算法如下：
// 在未处理的节点中找出开销最小的节点
const find_lowest_cost_node = (costs) => {
// 最小开销一开始要设置无穷大，这样所有的都会比它小
let lowest_cost = Infinity;
let lowest_cost_node = undefined;
for (let node in costs) {
const cost = costs[node];
// 如果当前开销小于最小开销并且当前节点未处理过
if (cost < lowest_cost && !processed.include(node)) {
lowest_cost = cost;
lowest_cost_node = node
}
}
return lowest_cost_node;
};
const node = find_lowest_cost_node(costs)
while (node) {
const cost = costs[node];
const neighbors = graph[node];
for(let n in neighbors) {
const new_cost = cost + neighbors[n];
// 如果经当前节点前往邻居更近
if (costs[n] > new_cost) {
// 就更新该邻居的开销
costs[n] = new_cost;
// 同时将邻居的父节点设置为当前节点
parents[n] = node;
}
}
// 将当前节点标记为处理过
processed.push(node);
node = find_lowest_cost_node(costs)
}
通过图例查看上面的代码具体流程
网友评论