贝尔曼福特算法(bellman ford)可以找到从目标节点到加权图其他节点的最短路径。这一点和dijkstra算法很相似，贝尔曼福特算法可以处理负权重的图，从实现来看也相对简单。
贝尔曼福特算法原理详解
贝尔曼福特算法通过高估从起始顶点到所有其他顶点的路径长度，迭代寻找比高估路径更短的新路径。
因为我们要记录每个节点的路径距离，可以将其存储在大小为n的数组中，n也代表了节点的数量。
实例图
立即学习“Python免费学习笔记（深入）”；
立即学习“Python免费学习笔记（深入）”；
1、选择起始节点，并无限指定给其他所有顶点，记录路径值。
立即学习“Python免费学习笔记（深入）”；
立即学习“Python免费学习笔记（深入）”；
2、访问每条边，并进行松弛操作，不断更新最短路径。
立即学习“Python免费学习笔记（深入）”；
立即学习“Python免费学习笔记（深入）”；
3、我们需要这样做N-1次，因为在最坏的情况下，最短节点路径长度可能需要重新调整N-1次。
立即学习“Python免费学习笔记（深入）”；
立即学习“Python免费学习笔记（深入）”；
4、注意右上角的节点是如何调整其路径长度的。
立即学习“Python免费学习笔记（深入）”；
立即学习“Python免费学习笔记（深入）”；
5、在所有节点都有路径长度之后，再检查是否存在负环路。
立即学习“Python免费学习笔记（深入）”；
立即学习“Python免费学习笔记（深入）”；
Python实现贝尔曼福特算法
class Graph: def __init__(self, vertices): self.V = vertices # Total number of vertices in the graph self.graph = [] # Array of edges def add_edge(self, s, d, w): self.graph.append([s, d, w]) def print_solution(self, dist): print("Vertex Distance from Source") for i in range(self.V): print("{0}{1}".format(i, dist[i])) def bellman_ford(self, src): dist = [float("Inf")] * self.V dist[src] = 0 for _ in range(self.V - 1): for s, d, w in self.graph: if dist[s] != float("Inf") and dist[s] + w
登录后复制
以上就是详解贝尔曼福特算法并用Python实现的详细内容，更多请关注【创想鸟】其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至253000106@qq.com举报，一经查实，本站将立刻删除。
发布者：PHP中文网，转转请注明出处：https://www.chuangxiangniao.com/p/2212954.html
