1. 最短路径问题
-
最短路问题(Shortest Path Problem,SPP)是图论的一个经典问题,其目的在于寻找网络中任意两个节点间的最短路径,这里的最短可以衍生为距离最短、费用最小、时间最短等一系列度量。当前的涌现了很多最短路径的变种,如带资源约束的最短路径问题(Shortest Path Problem with Resource Constraints, SPPRC)等;
-
数学模型
m i n ∑ ( i , j ) ∈ A c i j x i j ∑ j ∈ V x i j − ∑ j ∈ V x j i = { − 1 , i = s 0 , i ≠ s a n d i ≠ t 1 , i = t min\sum_{(i,j)\in A}{c_{ij} x_{ij}}\\ \sum_{j \in V}x_{ij} - \sum_{j\in V}x_{ji} = \begin{cases} -1, & {i = s } \\ 0, & {i \neq s \quad and \quad i \neq t}\\ 1, & {i=t}\\ \end{cases} min(i,j)∈A∑cijxijj∈V∑xij−j∈V∑xji=⎩ ⎨ ⎧−1,0,1,i=si=sandi=ti=t-
x i j x_{ij} xij: 0-1决策变量, x i j = 1 x_{ij}=1 xij=1表示经过弧 ( i , j ) (i, j) (i,j), x i j = 0 x_{ij}=0 xij=0表示不经过弧 ( i , j ) (i, j) (i,j)
-
c i j c_{ij} cij: 弧 ( i , j ) (i, j) (i,j)上的权重
-
A A A: 所有弧的集合
-
V V V: 所有点的集合
-
s , t s, t s,t :分别表示源节点和结束节点
-
2. 求解算法
一般使用label algorithm 或solver求解最短路径问题,本文使用Dijkstra algorithm和开源的SCIP求解器分别求解SPP, 并做结果对比。
2.1 Label Algorithm
- 标签算法是求解最短路径算法的常见算法,一般被分为两类:Label Setting Algorithm(如Dijkstra、Dial、Heap)和Label Correcting Algorithm(如Bellman-Ford、FIFO、Deque),两者都是基于动态规划的思想,且都是精确性算法,得到解一定是最优解。
- 两者如何更新临时距离标签差异不同:Label Setting Algorithm,在每次迭代时将当前临时距离标签最小的更新为永久距离标签,直到所有的临时距离标签都更新为永久距离标签;而Label Correcting Algorithm在每次迭代时都有可能更新临时距离标签的值,直到最后一次迭代时所有的临时距离标签才成为永久距离标签;
- 以上的差异点导致标准Label Setting Algorithm不适用含有负环网络,如果网络中有负环,可以采用Label Correcting Algorithm,如Bellman-Ford算法求解;
2.1.1 Dijkstra algorithm
Dijkstra算法本质上结合了贪心算法 + 动态规划的思想,关于其理论部分就不在此赘述,详细算法步骤见代码注释
- Dijkstra算法是求一个特定起点到其他所有顶点的最短路径,也称为单源最短路径算法
- 算法时间复杂度一般是 O ( n 2 ) O(n^2) O(n2)
- Dijkstra algorithm由于属于Label Setting Algorithm,所以不适用含有负权网络
2.1.2 python代码实现Dijkstra算法
python实现Dijkstra两种方式:
- 简洁一点,直接使用networkx提供了dijkstra算法的接口,只要定义带权重的图结构即可
- 基于图结构,使用python实现算法步骤
两种方式python代码实现如下:
import numpy as np
import matplotlib.pyplot as plt
import networkx as nx
import time
import pyscipopt as opt
def print_fun_run_time(func):
def wrapper(*args, **kwargs):
local_time = time.time()
func(*args, **kwargs)
print('current function [%s] run time is %.4f'%(func.__name__, time.time()-local_time))
return wrapper
def pic_graph(Nodes, Arcs):
"""
可视化图,节点的相对位置可能改变
"""
np.random.seed(1)
# 定义有向图
Graph = nx.DiGraph()
# 定义节点
for node in Nodes:
Graph.add_node(node, min_dis=0, previous_node=None, node_name=node)
# 定义弧
for (from_node, to_node), weight in Arcs.items():
Graph.add_edge(from_node, to_node, weight=weight)
plt.figure(figsize=(7, 5), dpi=100)
pos = nx.spring_layout(Graph)
nx.draw_networkx(Graph, pos)
node_labels = nx.get_node_attributes(Graph, 'node_name')
nx.draw_networkx_labels(Graph, pos, labels=node_labels)
edge_labels = nx.get_edge_attributes(Graph, 'weight')
nx.draw_networkx_edge_labels(Graph, pos, edge_labels=edge_labels)
plt.savefig('./spp_grap.png')
plt.show()
return True
def prepare_data():
# 测试数据: 邻接矩阵标识图结构,其中极大值1000表示不连通, 测试数据包含11个节点
matrix = np.array([[0, 2, 8, 1, 1000, 1000, 1000, 1000, 1000, 1000, 1000],
[2, 0, 6, 1000, 1, 1000, 1000, 1000, 1000, 1000, 1000],
[8, 6, 0, 7, 5, 1, 2, 1000, 1000, 1000, 1000],
[1, 1000, 7, 0, 1000, 1000, 9, 1000, 1000, 1000, 1000],
[1000, 1, 5, 1000, 0, 3, 1000, 2, 1000, 1000, 1000],
[1000, 1000, 1, 1000, 3, 0, 4, 1000, 6, 1000, 1000],
[1000, 1000, 2, 9, 1000, 4, 0, 1000, 3, 1, 1000],
[1000, 1000, 1000, 1000, 2, 1000, 1000, 0, 7, 1000, 9],
[1000, 1000, 1000, 1000, 1000, 6, 3, 7, 0, 1, 2],
[1000, 1000, 1000, 1000, 1000, 1000, 1, 1000, 1, 0, 4],
[1000, 1000, 1000, 1000, 1000, 1000, 1000, 9, 2, 4, 0]])
# 转换数据(只是为了方便理解,不为效率), 获取不包含本节点且连通的点及弧
row, col = np.where((matrix != 1000) & (matrix != 0))
Nodes = list(np.unique(np.unique(np.append(row, col)) + 1).astype('str'))
Arcs = {}
for i in range(len(row)):
Arcs[str(row[i] + 1), str(col[i] + 1)] = matrix[row[i], col[i]]
print('Nodes:\n', Nodes)
print('Arcs:\n', Arcs)
return Nodes, Arcs
@print_fun_run_time
def networkx_dijkstra(Nodes, Arcs, source, target):
"""
networkx提供了dijkstra算法的方法的封装,只要定义图结构即可。感兴趣可以学一下networkx的源码。
"""
Graph = nx.DiGraph()
# 添加节点
for node in Nodes:
Graph.add_node(node, min_dis=0, previous_node=None, node_name=node)
# 添加带权重的边
for (from_node, to_node), weight in Arcs.items():
Graph.add_weighted_edges_from([(from_node, to_node, weight)])
path = nx.dijkstra_path(Graph, source=source, target=target)
distance = nx.dijkstra_path_length(Graph, source=source, target=target)
print(f'节点 {source} 到 {target} 的路径={path}, 最短距离={distance}')
return True
@print_fun_run_time
def Dijkstra(Nodes, Arcs, source, target):
"""
Parameters
----------
Nodes: list
the set of node
Arcs: dict
key: pairs of node (from node, end node)
value: weight
source : node
Starting node
target : node
Ending node
Returns
-------
path : list
List of nodes in the shortest path
distance: Float
The short distance from source to target
"""
# ========== 数据结构 ==========
# 定义有向图
Graph = nx.DiGraph()
# 定义节点
for node in Nodes:
Graph.add_node(node, min_dis=0, previous_node=None, node_name=node)
# 定义弧
for (from_node, to_node), weight in Arcs.items():
Graph.add_edge(from_node, to_node, weight=weight)
# ========== 算法开始 ==========
# 初始化未探索节点集合: 初始时为所有节点集合
tmp_set = list(Graph.nodes())
# 初始化当前节点及所有节点的最短距离:起始点作为当前节点,并将起始点的最短路径置为0,其他节点距离置为无穷大
current_node = source
for node in tmp_set:
if (node == source):
Graph.nodes[node]['min_dis'] = 0
else:
Graph.nodes[node]['min_dis'] = np.inf
# 算法终止条件: 所有节点均被探索
while (len(tmp_set) > 0):
# 选择未探索的节点中的最短路径的节点作为新的当前节点
min_dis = np.inf
for node in tmp_set:
if (Graph.nodes[node]['min_dis'] < min_dis):
current_node = node
min_dis = Graph.nodes[node]['min_dis']
# 删除已探索的节点
if (current_node != None):
tmp_set.remove(current_node)
"""
循环判断当前节点所有相邻的节点:
1. 计算当前节点的最小值 + 相邻节点的权重的和,
2. 若小于相邻节点的最小距离,则更新相邻节点的最小距离,并标记相邻节点的前一个节点为当前节点
"""
for neighbor_node in Graph.successors(current_node):
arc = (current_node, neighbor_node)
dis_t = Graph.nodes[current_node]['min_dis'] + Graph.edges[arc]['weight']
if (dis_t < Graph.nodes[neighbor_node]['min_dis']):
Graph.nodes[neighbor_node]['min_dis'] = dis_t
Graph.nodes[neighbor_node]['previous_node'] = current_node
# ========== 获取结果 ==========
"""
获取结果:
1. 结束节点上更新的最短距离即为整个最短路径的距离
2. 根据结束节点回溯, 依次找到其上一个节点
"""
distance = Graph.nodes[target]['min_dis']
current_node = target
path = [current_node]
while (current_node != source):
current_node = Graph.nodes[current_node]['previous_node']
path.insert(0, current_node)
print(f'节点 {source} 到 {target} 的路径={path}, 最短距离={distance}')
return True
if __name__ == '__main__':
source = '1' # starting node
target = '11' # ending node
# 测试数据
Nodes, Arcs = prepare_data()
# 可视化图
pic_graph(Nodes, Arcs)
# 方式1: 使用networkx提供了dijkstra算法的方法的封装
networkx_dijkstra(Nodes, Arcs, source, target)
# 方式2: python实现Dijkstra算法求解最短路径问题
Dijkstra(Nodes, Arcs, source, target)
2.2 python调用SCIP求解器求解最短路径问题
代码实现可见之前写的博客 python调用求解器SCIP求解最短路径问题(Shortest Path Problem)
3. 算法结果
参考文献
Dijkstra E W . A Note on Two Problems in Connection with Graphs[J]. Numerische Mathematics, 1959.文章来源:https://www.toymoban.com/news/detail-491605.html
Martins E . On a multicriteria shortest path problem[J]. European Journal of Operational Research, 1984, 16(2):236-245.文章来源地址https://www.toymoban.com/news/detail-491605.html
到了这里,关于python实现Dijkstra算法求解最短路径问题(Shortest Path Problem)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!