算法图解中简单的介绍了两个算法:广度搜索优先和狄克斯特拉算法。用来查找最短路径,这个指的不是物理意义上的最短路径,后文便知。
问题
digraph {
label=加权有向图
rankdir = LR
{rank=same A B}
S -> A[label=6]
S -> B[label=2]
B -> A [label=3]
A -> E[label=1]
B -> E[label=5]
}
现在要解决从 S 到 E 最短路径的问题,如何最短的时间到达 E,图中的数字代表了需要消耗的时间。
图
一个图用来代表二维平面内的连接,上面例子中,圆的代表了 节点(Node),箭头代表了 边(Edge),数字代表了权重(Weight)。
无向图,其实就是节点间有两条边:
graph {
label=无向图
rankdir = LR
A -- B
}
其实它等于:
digraph {
label=有向图这其实也是一个环
A -> B
B -> A
}
广度优先算法
这个算法解决两个问题:
- S 到 E 有没有最短路径
- S 到 E 的最短路径是什么
实际上就是解决例子中,如何经过最少的节点来达到 E。
狄克斯特拉算法
这个问题要解决的是如何通过最的时间从 S 到达 E。
它包括 4 个步骤:
- 找出开销最小的节点(这里的开销是时间)。
- 更新起点到此节点各邻居的开销。
- 重复 1,2,直到所有节点已经处理完毕。
- 计算最终路径
通过代码来说明:
graph = {} graph['S'] = {} graph['S']['A'] = 6 graph['S']['B'] = 2
graph['A'] = {} graph['A']['E'] = 1
graph['B'] = {} graph['B']['E'] = 5 graph['B']['A'] = 3
graph['E'] = {}
costs = {} costs['A'] = 6 costs['B'] = 2 costs['E'] = float('inf')
parents = {} parents['A'] = 'S' parents['B'] = 'S' parents['E'] = 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: cost = costs[node] neighbors = graph[node] for n in neighbors.keys(): new_cost = cost + neighbors[n] if new_cost < costs[n]: costs[n] = new_cost parents[n] = node processed.append(node) node = find_lowest_cost_node(costs) path = []
s = 'E' path.append(s) while True: if s not in parents: break s = parents[s] path.insert(0, s) print('->'.join(path))
|
这个算法在有负权边的时候,会失效,这时候需要使用:贝尔曼-福德算法
这些代码在实际运用中不会这样搞,而是只需要传递一个 图,开始节点,终止节点 就能返回结果来,改造一下:
graph = { 'S': {'A': 5, 'B': 2}, 'A': {'C': 4, 'D': 2}, 'B': {'A': 8, 'D': 7}, 'C': {'E': 3, 'D': 6}, 'D': {'E': 1}, 'E': {}, }
def do(graph: dict, s, e): costs = {} parents = {} processed = [] parents[e] = None costs[e] = float('inf')
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
def find_path(parents): ''' 查找路径 ''' path = [] node = e path.append(node) while True: if node not in parents: break node = parents[node] path.insert(0, node) print('->'.join(path))
for n, v in graph[s].items(): parents[n] = s costs[n] = v node = find_lowest_cost_node(costs) while node: cost = costs[node] neighbors = graph[node] for n in neighbors.keys(): new_cost = cost + neighbors[n] if n not in costs: parents[n] = node costs[n] = new_cost if new_cost < costs[n]: costs[n] = new_cost parents[n] = node processed.append(node) node = find_lowest_cost_node(costs) find_path(parents)
do(graph, 'S', 'E')
|