【核心算法8】最短路径问题
2020-12-22 11:27
标签：地图 pytho lse 核心 def app 概念 eve ESS 手机导航是怎么得出两个地点间的最短线路？把地图简化为一个加权图，然后利用这个加权图查找最短路径。 将地点看成节点，把道路看成边，整个地图就可看成一个加权图 如图所示公交车线路图，从A站到F站，如何知道坐车距离最短，可用迪克斯特朗算法。 迪克斯特朗算法，又被译为戴克斯特拉算法，它主要用于解决有向图的最短路径问题。 输入边的权重和一个起点，迪克斯特朗算法能够得出从该起点到任何其他节点的最短路径。 (权重不可为负) 观察这个公交车系统包括6个站点和连接车站的9条边。图中每条边上都标有距离，也就是权重。另外，每条边都是双向的，可以从一个车站到另一个车站，也可以从那一个车站回到这个车站。 迪克斯特朗算法的基本概念是，如果设定一个车站为起点，那么算法能够找出一个公交车系统中从该车站到任意车站的最短距离路线。主要特点是以起点为中心向外层层扩展，直到扩展到终点为止 图的定义 节点的定义 用代码将图实现 算法核心1：两个节点集合 定义连个节点集合：临时节点集合和永久节点集合 算法核心2：循环 一直循环两个步骤，它每循环一次都要确保局部最优 输出路线 从终点回溯到起点就可以得到最短路线 【核心算法8】最短路径问题 标签：地图 pytho lse 核心 def app 概念 eve ESS 原文地址：https://www.cnblogs.com/JoshuaP/p/13216346.html
迪克斯特朗算法
术语解释
术语
解释
图
一个图是由节点和连接这些节点的边组成
节点
一个小圆点，可以看成一个事物，站点，城市等
边
连接节点的直线和曲线
有向图
赋予边方向的图
权重
边的距离
前任节点
路线中连接节点的上一个节点
问题描述
思路解析
class Graph(object):
def __init__(self):
# 节点集合
self.nodes = set()
# 存储边集合的字典
self.edges = dict()
# 记录每条边的距离的集合
self.distances = {}
def add_node(self, node):
"""
增加节点
:param node:
:return:
"""
self.nodes.add(node)
def add_edge(self, from_node, to_node, distance):
"""
增加边
:param from_node: 起点
:param to_node: 终点
:param distance: 距离
:return:
"""
if from_node not in self.edges.keys():
self.edges[from_node] = [to_node]
else:
self.edges[from_node].append(to_node)
self.distances[(from_node, to_node)] = distance
class Node(object):
def __init__(self, name):
"""
:param name: 节点名称
"""
# 设定起始距离值为最大值
self.distance = sys.maxsize
# 起始节点的前任节点为空
self.predecessor = None
self.name = name
# 设定距离值
def set_distance(self, dist):
self.distance = dist
# 设定前任节点
def set_predecessor(self, pred):
self.predecessor = pred
# 获取距离值
def get_distance(self):
return self.distance
# 获取前任节点
def get_predecessor(self):
return self.predecessor
g = Graph()
g.add_node(Node(‘A‘))
g.add_node(Node(‘B‘))
g.add_node(Node(‘C‘))
g.add_node(Node(‘D‘))
g.add_node(Node(‘E‘))
g.add_node(Node(‘F‘))
g.add_edge(‘A‘, ‘B‘, 10)
g.add_edge(‘B‘, ‘A‘, 10)
g.add_edge(‘A‘, ‘C‘, 15)
g.add_edge(‘C‘, ‘A‘, 15)
...
g.add_edge(‘E‘, ‘F‘, 20)
g.add_edge(‘F‘, ‘E‘, 20)
permanent = set()
temporary = set()
# 算法开始把起始点加入临时节点集合
temporary.add(initial)
代码实现
import sys
class Graph(object):
def __init__(self):
# 节点集合
self.nodes = set()
# 存储边集合的字典
self.edges = dict()
# 记录每条边的距离的集合
self.distances = {}
def add_node(self, node):
"""
增加节点
:param node:
:return:
"""
self.nodes.add(node)
def add_edge(self, from_node, to_node, distance):
"""
增加边
:param from_node: 起点
:param to_node: 终点
:param distance: 距离
:return:
"""
if from_node not in self.edges.keys():
self.edges[from_node] = [to_node]
else:
self.edges[from_node].append(to_node)
self.distances[(from_node, to_node)] = distance
class Node(object):
def __init__(self, name):
"""
:param name: 节点名称
"""
# 设定起始距离值为最大值
self.distance = sys.maxsize
# 起始节点的前任节点为空
self.predecessor = None
self.name = name
# 设定距离值
def set_distance(self, dist):
self.distance = dist
# 设定前任节点
def set_predecessor(self, pred):
self.predecessor = pred
# 获取距离值
def get_distance(self):
return self.distance
# 获取前任节点
def get_predecessor(self):
return self.predecessor
def print_path(self, end, predecessor):
current = end
path = (end)
while current.predecessor != None:
path.add(current.predecessor)
current = current.predecessor
path.reverse()
def dijkstra(graph, initial, end):
permanent = set()
temporary = set()
temporary.add(initial)
initial.set_distance()
while temporary:
min_node = None
for node in temporary:
if min_node is None:
min_node = node
elif node.get_distance()