一、简介
前面章节介绍了使用广度优先搜索，设计找出段数最少的路径算法。但是路段最少并不表示速度最快，如果你需要找出最快的路径，就可以使用本章要介绍的狄克斯特拉算法 Dijkstra's algorithm
如下图，给每个路段都加上它的耗时
如果你使用广度优先搜索，你将找出起点到终点路段数最少的路径。
但使用狄克斯特拉算法,你就可以找出起点到终点耗时最少的路径。
狄克斯特拉算法用于每条边都有关联数字的图，这些数字称为权重。
带权重的图称为加权图，不带权重的图称为非加权图。计算非加权图中的最短路径，可使用广度优先搜索。计算加权图中的最短路径，可使用狄克斯特拉算法。
图还有可能有环，但狄克斯特拉算法只适用于有向无环图。
二、实现原理
如下图，使用狄克斯特拉算法计算最短路径。
要编写解决这个问题的代码，首先需要三个散列表。
表1、存储图中的所有节点和权重信息
表2、存储存储每个节点的开销
节点的开销指的是从起点出发前往该节点需要多长时间。对于还不知道的开销则设其为无穷大。
表3、父节点的散列表
最后，还需要一个数组，用于记录处理过的节点，因为对于同一个节点，你不用处理多次。
算法原理大概如下：
处理所有节点后，这个算法就结束了。
三、代码实现：
1、Python 3 ：
# the graph
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"] = {} # 终点没有任何邻居了
# the costs table
infinity = float("inf") # 表示无穷大
costs = {}
costs["a"] = 6
costs["b"] = 2
costs["fin"] = infinity
# the parents table
parents = {}
parents["a"] = "start"
parents["b"] = "start"
parents["fin"] = None
processed = [] # 记录处理过的节点
# 在未处理的节点中找出开销最小的节点
def find_lowest_cost_node(costs):
lowest_cost = float("inf")
lowest_cost_node = None
for node in costs: # 遍历所有节点
cost = costs[node]
if cost < lowest_cost and node not in processed: # 如果当前节点的开销更低且未处理过
lowest_cost = cost # 就将其视为开销最低的节点
lowest_cost_node = node
return lowest_cost_node
node = find_lowest_cost_node(costs)
while node is not None: # 所有节点都被处理过后结束
cost = costs[node]
neighbors = graph[node]
for n in neighbors.keys(): #遍历当前节点的所有邻居
new_cost = cost + neighbors[n]
if costs[n] > new_cost: # 如果经当前节点前往该邻居更近
costs[n] = new_cost # 就更新该邻居的开销
parents[n] = node # 同时将该邻居的父节点设置为当前节点
processed.append(node) # 将当前节点标记为处理过
node = find_lowest_cost_node(costs) # 找出接下来要处理的节点，并循环
print ("Cost from the start to each node:")
print (costs)
print (parents)
=============== 运行结果：===============
Cost from the start to each node:
{'a': 5, 'b': 2, 'fin': 6}
{'a': 'b', 'b': 'start', 'fin': 'a'}
2、PHP ：
$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"] = [];
# the costs table
$infinity = PHP_INT_MAX;
$costs = [];
$costs["a"] = 6;
$costs["b"] = 2;
$costs["fin"] = $infinity;
# the parents table
$parents = [];
$parents["a"] = "start";
$parents["b"] = "start";
$parents["fin"] = null;
$processed = [];
// 在未处理的节点中找出开销最小的节点
function findLowestCodeNode(array $costs) {
$lowestCost = PHP_INT_MAX;
$lowestCostNode = null;
global $processed;
foreach ($costs as $node => $cost) { //遍历所有节点
if ($cost < $lowestCost && !array_key_exists($node, $processed)) {
$lowestCost = $cost;
$lowestCostNode = $node;
}
}
return $lowestCostNode;
}
$node = findLowestCodeNode($costs);
while ($node) {
$cost = $costs[$node];
$neighbors = $graph[$node];
foreach (array_keys($neighbors) as $n) {
$newCost = $cost + $neighbors[$n];
if ($costs[$n] > $newCost) {
$costs[$n] = $newCost;
$parents[$n] = $node;
}
}
$processed[$node] = true;
$node = findLowestCodeNode($costs);
}
print("Cost from the start to each node:");
var_dump($costs);
var_dump($parents);
=============== 运行结果：===============
Cost from the start to each node:
array(3) {
["a"]=>
int(5)
["b"]=>
int(2)
["fin"]=>
int(6)
}
array(3) {
["a"]=>
string(1) "b"
["b"]=>
string(5) "start"
["fin"]=>
string(1) "a"
}
网友评论