求最短路径的三种算法: Ford, Dijkstra和Floyd
Bellman-Ford算法
Bellman-Ford是一种容易理解的单源最短路径算法, Bellman-Ford算法需要两个数组进行辅助:
dis[i]
: 存储顶点i到源点已知最短路径path[i]
: 存储顶点i到源点已知最短路径上, i的前一个顶点.
若图有n个顶点, 则图中最长简单路径长度不超过n-1, 因此Ford算法进行n-1次迭代确保获得最短路径.
Ford算法的每次迭代遍历所有边, 并对边进行松弛(relax)操作. 对边e进行松弛是指: 若从源点通过e.start到达e.stop的路径长小于已知最短路径, 则更新已知最短路径.
为了便于描述, 本文采用python实现算法. 首先实现两个工具函数:
INF = 1e6
def make_mat(m, n, fill=None):
mat = []
for i in range(m):
mat.append([fill] * n)
return mat
def get_edges(graph):
n = len(graph)
edges = []
for i in range(n):
for j in range(n):
if graph[i][j] != 0:
edges.append((i, j, graph[i][j]))
return edges
make_mat
用于初始化二维数组, get_edges
用于将图由邻接矩阵表示变换为边的列表.
接下来就可以实现Bellman-Ford算法了:
def ford(graph, v0):
n = len(graph)
edges = get_edges(graph)
dis = [INF] * n
dis[v0] = 0
path = [0] * n
for k in range(n-1):
for edge in edges:
# relax
if dis[edge[0]] + edge[2] < dis[edge[1]]:
dis[edge[1]] = dis[edge[0]] + edge[2]
path[edge[1]] = edge[0]
return dis, path
初始化后执行迭代和松弛操作, 非常简单.
由path[i]获得最短路径的前驱顶点, 逐次迭代得到从顶点i到源点的最短路径. 倒序即可得源点到i的最短路径.
def show(path, start, stop):
i = stop
tmp = [stop]
while i != start:
i = path[i]
tmp.append(i)
return list(reversed(tmp))
Ford算法允许路径的权值为负, 但是若路径中存在总权值为负的环的话, 每次经过该环最短路径长就会减少. 因此, 图中的部分点不存在最短路径(最短路径长为负无穷).
若路径中不存在负环, 则进行n-1次迭代后不存在可以进行松弛的边. 因此再遍历一次边, 若存在可松弛的边说明图中存在负环.
这样改进得到可以检测负环的Ford算法:
def ford(graph, v0):
n = len(graph)
edges = get_edges(graph)
dis = [INF] * n
dis[v0] = 0
path = [0] * n
for k in range(n-1):
for edge in edges:
# relax
if dis[edge[0]] + edge[2] < dis[edge[1]]:
dis[edge[1]] = dis[edge[0]] + edge[2]
path[edge[1]] = edge[0]
# check negative loop
flag = False
for edge in edges:
# try to relax
if dis[edge[0]] + edge[2] < dis[edge[1]]:
flag = True
break
if flag:
return False
return dis, path
Dijkstra算法
Dijkstra算法是一种贪心算法, 但可以保证求得全局最优解. Dijkstra算法需要和Ford算法同样的两个辅助数组:
dis[i]
: 存储顶点i到源点已知最短路径path[i]
: 存储顶点i到源点已知最短路径上, i的前一个顶点.
Dijkstra算法的核心仍然是松弛操作, 但是选择松弛的边的方法不同. Dijkstra算法使用一个小顶堆存储所有未被访问过的边, 然后每次选择其中最小的进行松弛.
def dijkstra(graph, v0):
n = len(graph)
dis = [INF] * n
dis[v0] = 0
path = [0] * n
unvisited = get_edges(graph)
heapq.heapify(unvisited)
while len(unvisited):
u = heapq.heappop(unvisited)[1]
for v in range(len(graph[u])):
w = graph[u][v]
if dis[u] + w < dis[v]:
dis[v] = dis[u] + w
path[v] = u
return dis, path
Floyd
floyd算法是采用动态规划思想的多源最短路径算法. 它同样需要两个辅助数组, 但作为多源最短路径算法, 其结构不同:
dis[i][j]
: 保存从顶点i到顶点j的已知最短路径, 初始化为直接连接path[i][j]
: 保存从顶点i到顶点j的已知最短路径上下一个顶点, 初始化为j
def floyd(graph):
# init
m = len(graph)
dis = make_mat(m, m, fill=0)
path = make_mat(m, m, fill=0)
for i in range(m):
for j in range(m):
dis[i][j] = graph[i][j]
path[i][j] = j
for k in range(m):
for i in range(m):
for j in range(m):
# relax
if dis[i][k] + dis[k][j] < dis[i][j]:
dis[i][j] = dis[i][k] + dis[k][j]
path[i][j] = path[i][k]
return dis, path
算法核心是遍历顶点k, i, j. 若从顶点i经过顶点k到达顶点j的路径, 比已知从i到j的最短路径短, 则更新已知最短路径.
相关文章
- [Unity3D+算法]一小时做个2048
- Java实现 蓝桥杯VIP 算法训练 幂方分解
- Java实现 蓝桥杯 算法提高 复数四则运算
- Java实现 蓝桥杯 算法训练 区间k大数
- Open3D(C++) 点到平面的ICP算法实现点云精配准
- 基于小生境粒子群优化算法的考虑光伏波动性的主动配电网有功无功协调优化(Matlab代码实现)
- 基于蚁群算法求解运钞车路径规划问题(Matlab代码实现)
- 蚁群优化算法解决TSP问题(Matlab代码实现)
- 基于RRT算法的最优动力学路径规划(Matlab代码实现)
- 基于蚁群算法的时延Petri网(ACOTPN)路径规划算法(Matlab代码实现)
- 基于球向量的粒子群优化(SPSO)算法在无人机路径规划中的实现(Matlab代码实现)
- 【路径规划】基于D*算法的移动机器人路径规划(Matlab代码实现)
- 使用HGS算法调整PD控制器增益的无人机动态性能数据——基于启发式的无人机路径跟踪优化(Matlab代码实现)
- 基于人工蜂群算法的新型概率密度模型无人机路径规划(Matlab代码实现)
- 数学建模学习(45):Dijkstra算法,图的最短路径和距离
- 基于Multi-Verse Optimizer(MVO)多元宇宙优化的DBSCAN数据聚类算法matlab仿真
- 基于GA算法的TSP最短路径搜索matlab仿真
- m基于sift特征提取和模板匹配的车标识别算法matlab仿真
- C语言使用技巧(二十二):算法技巧:while(1)与if循环的循环扣圈搜索与路径节点搜索
- Bellman-Ford算法——为什么要循环n-1次?图有n个点,又不能有回路,所以最短路径最多n-1边。又因为每次循环,至少relax一边所以最多n-1次就行了!
- 一致性问题和Raft一致性算法——一致性问题是无法彻底解决的,可以说一个分布式系统可靠性达到99.99…%,但不能说它达到了100%
- 经典树与图论(最小生成树、哈夫曼树、最短路径问题---Dijkstra算法)
- Python小白的数学建模课-16.最短路径算法
- 最短路径(Floyd算法,弗洛伊德算法,多源最短路径)
- ML之KG:基于MovieLens电影评分数据集利用基于知识图谱的推荐算法(networkx+基于路径相似度的方法)实现对用户进行Top电影推荐案例
- Java 算法合并 Geoserver 切片生成指北针图片:高效、优雅解决地图数据可视化问题
- 路径规划算法:A*算法 - 附代码
- 【图像配准】SIFT算法原理及二图配准拼接