• 技术文章 >Python技术 >Python基础教程

    python Bellman-Ford算法是什么

    小妮浅浅小妮浅浅2021-09-29 09:31:08原创2697

    说明

    1、Bellman-Ford算法是包含负权图的单源最短路径算法。

    算法原理是对图进行V-1放松操作,获得所有可能的最短路径。

    2、Bellman-Ford算法可以处理负面边缘。它的基本操作扩展是在深度上搜索,而放松操作是在广度上搜索。

    它可以在不影响结果的情况下操作负面边缘。

    Bellman-Ford算法效率低,时间复杂度高达o(V*E),v、e分别为顶点和边数。SPFA是Bellman-Ford的队列优化,通过维护队列可以大幅度减少重复计算,时间复杂度为o(k*E)。

    实例

    1

    2

    3

    4

    5

    6

    7

    8

    9

    10

    11

    12

    13

    14

    15

    16

    17

    18

    19

    20

    21

    22

    23

    24

    25

    26

    27

    28

    29

    30

    31

    32

    33

    34

    35

    36

    37

    38

    def bellman_ford( graph, source ):

         

        distance = {}

        parent = {}

         

        for node in graph:

            distance[node] = float( 'Inf' )

            parent[node] = None

        distance[source] = 0

      

        for i in range( len( graph ) - 1 ):

            for from_node in graph:

                for to_node in graph[from_node]:

                    if distance[to_node] > graph[from_node][to_node] + distance[from_node]:

                        distance[to_node] = graph[from_node][to_node] + distance[from_node]

                        parent[to_node] = from_node

      

        for from_node in graph:

            for to_node in graph[from_node]:

                if distance[to_node] > distance[from_node] + graph[from_node][to_node]:

                    return None, None

      

        return distance, parent

      

    def test():

        graph = {

            'a': {'b': -1, 'c':  4},

            'b': {'c':  3, 'd':  2, 'e':  2},

            'c': {},

            'd': {'b':  1, 'c':  5},

            'e': {'d': -3}

        }

        distance, parent = bellman_ford( graph, 'a' )

        print distance

        print parent

      

    if __name__ == '__main__':

        test()

    以上就是python Bellman-Ford算法的介绍,希望对大家有所帮助。更多Python学习指路:python基础教程

    本文教程操作环境:windows7系统、Python 3.9.1,DELL G3电脑。

    专题推荐:python bellman-ford算法
    上一篇:python最短路径问题的介绍 下一篇:python Floyd算法是什么

    相关文章推荐

    • python迭代器的取值方法• python迭代器的优缺点• python使用Pyecharts绘制疫情分布图• 如何查看python解释器的路径• python用户输入的方法• python if-elif-else语句是什么• python列表中if语句的用途• Python f-string字符串格式化的介绍• Python Dijkstra算法是什么• python最短路径问题的介绍

    全部评论我要评论

    © 2021 Python学习网 苏ICP备2021003149号-1

  • 取消发布评论
  • 

    Python学习网