美文网首页
算法_Dijkstra_Python

算法_Dijkstra_Python

作者: 计算士 | 来源:发表于2015-05-29 01:55 被阅读2183次

本文用到的包

import networkx as nx

考虑如下网络


流网络示意图流网络示意图

这个网络的构建代码是

G=nx.DiGraph()
G.add_edge(0,1,weight=80)
G.add_edge(1,2,weight=50)
G.add_edge(1,3,weight=30)
G.add_edge(3,2,weight=10)
G.add_edge(2,4,weight=20)
G.add_edge(2,5,weight=30)
G.add_edge(4,5,weight=10)
G.add_edge(5,3,weight=5)
G.add_edge(2,6,weight=10)
G.add_edge(4,6,weight=10)
G.add_edge(3,6,weight=25)
G.add_edge(5,6,weight=35)

可视化绘制使用了Processing,制图代码在这里

定义如下函数

def Dijkstra(G,start,end):
    RG = G.reverse(); dist = {}; previous = {}
    for v in RG.nodes():
        dist[v] = float('inf')
        previous[v] = 'none'
    dist[end] = 0
    u = end
    while u!=start:
        u = min(dist, key=dist.get)           
        distu = dist[u]
        del dist[u]
        for u,v in RG.edges(u):
            if v in dist:
                alt = distu + RG[u][v]['weight']
                if alt < dist[v]:
                    dist[v] = alt
                    previous[v] = u
    path=(start,)
    last= start
    while last != end:
        nxt = previous[last]
        path += (nxt,)
        last = nxt
    return path

使用这个函数寻找0与6之间的最小权重路径

Dijkstra(G,0,6)

其结果是

(0, 1, 3, 2, 6)

相关文章

  • 算法_Dijkstra_Python

    本文用到的包 考虑如下网络 这个网络的构建代码是 可视化绘制使用了Processing,制图代码在这里。 定义如下...

  • 匈牙利算法

    算法思想 算法流程 算法步骤 算法实现 python 算法应用

  • web开发需要知道的几个算法

    算法分类 快速排序算法 深度优先算法 广度优先算法 堆排序算法 归并排序算法

  • 机器学习算法

    机器学习的算法分监督算法和无监督 算法。监督算法包括回归算法,神经网络,SVM;无监督算法包括聚类算法,降维算法。...

  • 字符串匹配

    BF 算法和 RK 算法BM 算法和 KMP 算法

  • 垃圾回收算法有几种类型? 他们对应的优缺点又是什么?

    常见的垃圾回收算法有: 标记-清除算法、复制算法、标记-整理算法、分代收集算法 标记-清除算法 标记—清除算法包括...

  • 头条-手撕代码

    [toc] 图算法 以及最短路径算法 树算法 手写LRU 排序算法 链表算法

  • 关于一些算法

    我们平常说的算法按照使用方向加密算法,排序算法,搜索算法,优化算法,音视频处理算法,图片处理算法 1.加密解密算法...

  • 给我巨大影响的技术书籍

    算法《算法概论》《算法设计与分析基础》 Anany Levitin《算法引论》Udi Manber《算法导论》《什...

  • 缓存相关

    cache淘汰算法:LIRS 算法 缓存那些事 Redis缓存淘汰算法,LRU算法,LRU算法讲解

网友评论

      本文标题:算法_Dijkstra_Python

      本文链接:https://www.haomeiwen.com/subject/oewrqttx.html