数学模型

Wang Haihua

🍈 🍉🍊 🍋 🍌

---

最短路径问题

最短路径问题是图论研究中的经典算法问题，用于计算图中一个顶点到另一个顶点的最短路径。

最短路径问题有几种形式：确定起点的最短路径，确定终点的最短路径，确定起点和终点的最短路径，全局最短路径问题。

如果问题不涉及相邻顶点间的距离，要计算从起点到终点的最短路径及对应的最短路径长度，是指这条路径从起点到终点有几步（站），在图论中称为最短路径长度。但是，如果问题给出相邻顶点之间的道路长度或距离，姑且称为各路段的距离，要计算从起点到终点的最短路径及对应的最短距离，显然并不是要找经过最少步数的路径，而是在找路径中各路段的距离之和最小的路径，在图论中称为最短加权路径长度——这里权重是路段距离。

相邻顶点的连接边的权，不仅可以是路段距离，也可以是时间、费用等指标。问题就变成寻求最短时间、最低成本的路径，这实际上也是最短加权路径长度问题。

最短路径的常用算法

求解最短路径长度的常用算法是 Dijkstra 算法、Bellman-Ford 算法和Floyd 算法，另外还有启发式算法 A*。

Dijkstra 算法

Dijkstra 算法是经典的最短路径算法，在数据结构、图论、运筹学中都是教学的基本算法。有趣的是，在数据结构中 Dijkstra 算法通常是按贪心法讲述，而在运筹学中则被认为是动态规划法。

Dijkstra算法从起点开始，采用贪心法策略，每次遍历距离起点最近且未访问过的邻接顶点， 层层扩展直到终点为止。

Dijkstra算法可以求出加权最短路径的最优解，算法的时间复杂度为 O(n^2)。如果边数远小于 n^2，可以用堆结构将复杂度降为O((m+n)log(n))。

Dijkstar算法不能处理负权边，这是由于贪心法的选择规则决定的。

Bellman-Ford 算法

Bellman-Ford 算法是求含负权图的单源最短路径算法。算法原理是对图进行 V-1次松弛操作，得到所有可能的最短路径。

Bellman-Ford 算法可以处理负权边。其基本操作“拓展”是在深度上搜索，而“松弛”操作则在广度上搜索，因此可以对负权边进行操作而不影响结果。

Bellman-Ford 算法的效率很低，时间复杂度高达 O(VE)，V、E 分别是顶点和边的数量。SPFA 是 Bellman-Ford 的队列优化，通过维护一个队列极大地减少了重复计算，时间复杂度为 O(kE) 。

Dijkstra 算法在求解过程中，起点到各顶点的最短路径求出后就不变了。Bellman算法在求解过程中，每次循环都要修改所有顶点间的距离，起点到各顶点最短路径一直要到算法结束才确定。

Floyd 算法

Floyd 算法又称插点法，运用动态规划思想求解有权图中多源点之间最短路径问题。算法从图的带权邻接矩阵开始，递归地进行 n 次更新得到图的距离矩阵，进而可以得到最短路径节点矩阵。

Floyd 算法的时间复杂度为 O(n^3)，空间复杂度为 O(n^2)。算法时间复杂度较高，不适合计算大量数据。Floyd 算法的优点是可以一次性求解任意两个节点之间的最短距离，对于稠密图的效率高于执行 V 次 Dijkstra算法。

Floyd 算法可以处理负权边。

Floyd 算法号称只有 5行代码，我们来欣赏一下： for(k=0;k<n;k++)//中转站0~k for(i=0;i<n;i++) //i为起点 for(j=0;j<n;j++) //j为终点 if(d[i][j]>d[i][k]+d[k][j])//松弛操作 d[i][j]=d[i][k]+d[k][j];

A* 算法

A*算法是一种静态路网中求解最短路径最有效的直接搜索方法。

A*算法是启发式算法，采用最佳优先（Best-first）搜索策略，基于估价函数对每个搜索位置的评估结果，猜测最好的位置优先进行搜索。

A*算法极大地减少了低质量的搜索路径，因而搜索效率很高，比传统的路径规划算法实时性更高、灵活性更强；但是，A*算法找到的是相对最优路径，不是绝对的最短路径，适合大规模、实时性高的问题。

最短路径算法的选择

• 需要求解任意两个节点之间的最短距离，使用 Floyd 算法；
• 只要求解单源最短路径问题，有负权边时使用 Bellman-Ford 算法，没有负权边时使用 Dijkstra 算法；
• A*算法找到的是相对最优路径，适合大规模、实时性高的问题。

案例(城市间机票价格问题)

已知 6个城市之间的机票票价如矩阵所示（无穷大表示没有直航），求城市 A 到其它城市的票价最便宜的路径及票价。其中若值为0代表两地之间无直航，若值不为零，表示票价。

	A	B	C	D	E	F
A	0	50	0	40	25	10
B	50	0	15	20	0	25
C	0	15	0	10	20	0
D	40	20	10	0	10	25
E	25	0	20	10	0	55
F	10	25	0	25	55	0

---

import numpy as np
import pulp as lp
import pandas as pd
import matplotlib.pyplot as plt
from model_insight.load_datasets import load_tickets
import networkx as nx

tickets = load_tickets()

tickets

	A	B	C	D	E	F
A	0	50	0	40	25	10
B	50	0	15	20	0	25
C	0	15	0	10	20	0
D	40	20	10	0	10	25
E	25	0	20	10	0	55
F	10	25	0	25	55	0

# # 从Pandas数据格式（顶点邻接矩阵）创建 NetworkX 图
# # from_pandas_adjacency(df, create_using=None) # 邻接矩阵，n行*n列，矩阵数据表示权重
plt.figure(figsize=(7,3))
G = nx.from_pandas_adjacency(tickets)  # 由 pandas 顶点邻接矩阵 创建 NetworkX 图

# 计算最短路径：注意最短路径与最短加权路径的不同

for i in tickets.index:
    minWPathA = nx.bellman_ford_path(G, source='A', target=i)  # 顶点 0 到其它顶点的最短加权路径
    lMinPathA = nx.bellman_ford_path_length(G, source='A', target=i)  #最短加权路径长度
    print("城市 A 到 城市 {} 机票票价最低的路线为: {}，票价总和为：{}".format(i, minWPathA, lMinPathA))

nx.draw_shell(G, with_labels=True, node_color='r', edge_color='orange', font_color='w', width=1)
plt.show()

城市 A 到 城市 A 机票票价最低的路线为: ['A']，票价总和为：0
城市 A 到 城市 B 机票票价最低的路线为: ['A', 'F', 'B']，票价总和为：35
城市 A 到 城市 C 机票票价最低的路线为: ['A', 'E', 'C']，票价总和为：45
城市 A 到 城市 D 机票票价最低的路线为: ['A', 'E', 'D']，票价总和为：35
城市 A 到 城市 E 机票票价最低的路线为: ['A', 'E']，票价总和为：25
城市 A 到 城市 F 机票票价最低的路线为: ['A', 'F']，票价总和为：10