详解贝尔曼福特算法并用Python实现

WBOY
发布: 2024-01-22 19:39:13
转载
1282人浏览过

贝尔曼福特算法(bellman ford)可以找到从目标节点到加权图其他节点的最短路径。这一点和dijkstra算法很相似,贝尔曼福特算法可以处理负权重的图,从实现来看也相对简单。

贝尔曼福特算法原理详解

贝尔曼福特算法通过高估从起始顶点到所有其他顶点的路径长度,迭代寻找比高估路径更短的新路径。

因为我们要记录每个节点的路径距离,可以将其存储在大小为n的数组中,n也代表了节点的数量。

实例图

立即学习Python免费学习笔记(深入)”;

贝尔曼福特算法概念详解 Python实现贝尔曼福特算法

立即学习Python免费学习笔记(深入)”;

1、选择起始节点,并无限指定给其他所有顶点,记录路径值。

立即学习Python免费学习笔记(深入)”;

贝尔曼福特算法概念详解 Python实现贝尔曼福特算法

立即学习Python免费学习笔记(深入)”;

2、访问每条边,并进行松弛操作,不断更新最短路径。

立即学习Python免费学习笔记(深入)”;

贝尔曼福特算法概念详解 Python实现贝尔曼福特算法

立即学习Python免费学习笔记(深入)”;

3、我们需要这样做N-1次,因为在最坏的情况下,最短节点路径长度可能需要重新调整N-1次。

立即学习Python免费学习笔记(深入)”;

贝尔曼福特算法概念详解 Python实现贝尔曼福特算法

立即学习Python免费学习笔记(深入)”;

4、注意右上角的节点是如何调整其路径长度的。

立即学习Python免费学习笔记(深入)”;

贝尔曼福特算法概念详解 Python实现贝尔曼福特算法

立即学习Python免费学习笔记(深入)”;

5、在所有节点都有路径长度之后,再检查是否存在负环路。

立即学习Python免费学习笔记(深入)”;

贝尔曼福特算法概念详解 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}\t\t{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 < dist[d]:
                    dist[d] = dist[s] + w

        for s, d, w in self.graph:
            if dist[s] != float("Inf") and dist[s] + w < dist[d]:
                print("Graph contains negative weight cycle")
                return

        self.print_solution(dist)

g = Graph(5)
g.add_edge(0, 1, 5)
g.add_edge(0, 2, 4)
g.add_edge(1, 3, 3)
g.add_edge(2, 1, 6)
g.add_edge(3, 2, 2)

g.bellman_ford(0)
登录后复制

以上就是详解贝尔曼福特算法并用Python实现的详细内容,更多请关注php中文网其它相关文章!

python速学教程(入门到精通)
python速学教程(入门到精通)

python怎么学习?python怎么入门?python在哪学?python怎么学才快?不用担心,这里为大家提供了python速学教程(入门到精通),有需要的小伙伴保存下载就能学习啦!

下载
相关标签:
来源:网易伏羲网
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
最新问题
开源免费商场系统广告
热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板
关于我们 免责申明 意见反馈 讲师合作 广告合作 最新更新
php中文网:公益在线php培训,帮助PHP学习者快速成长!
关注服务号 技术交流群
PHP中文网订阅号
每天精选资源文章推送
PHP中文网APP
随时随地碎片化学习
PHP中文网抖音号
发现有趣的

Copyright 2014-2025 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号