比特微 vue 分库查询 Redis 反射 log4j encryption deployment icons Modernizr 多商户商城模板 进销存源码 jq获取最后一个子元素 oracle查看数据库状态 matlab生成对角矩阵 matlab区分大小写吗 python编程教程 python文件 python安装程序 java获取当前月份 怎么配置java环境 java正则表达式详解 java运算 学java基础 java匿名函数 java集合类 java中的集合 java异常处理 liunx命令大全 linux服务器 战地女记者 丁丁下载 pdf拆分工具 风火云 js获取父节点 oem修改器 16进制编辑器 wow怎么赚钱 战斗的召唤 vue路由跳转
当前位置: 首页 > 学习教程  > 编程语言

图论基础知识以及相应算法

2020/7/24 11:21:14 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

一.基础知识

 

         有向图   无向图

二.Dijkstra算法

Dijkstra算法用于解决单源最短路问题,所谓单源最短路就是指定一个起点,求出这个起点到其它所有点的最短路。

示例:求M到各个顶点的最短路径

先构建邻接矩阵Adjacent, 初始状态dist[1~n] = inf, dist[M]=0,顶点更新状态vst[1~n] = 0

以点M为起点:

dist[M] = 0    vst[M] = 0
dist[W] = inf  vst[W] = 0
dist[E] = inf  vst[E] = 0
dist[D] = inf  vst[D] = 0
dist[X] = inf  vst[X] = 0

找出dist中值最小且未被使用的点,发现dist[M]=0最小,且vst[M]=0,未被使用,故将M作为新的起点.
找出所有M可达的顶点,为X、W、E
dist[X]=inf > 0+10 ,更新dist[X]=10
dist[W]=inf > 0+5 ,更新dist[W]=5
dist[E]=inf > 0+8 ,更新dist[E]=8
M已被使用,vst[M]=1

dist[M] = 0    vst[M] = 1
dist[W] = 5    vst[W] = 0
dist[E] = 8    vst[E] = 0
dist[D] = inf  vst[D] = 0
dist[X] = 10   vst[X] = 0

依次遍历每个顶点........ 

#Dijkstra算法,就是依次让每个顶点作为起点,更新最短路的过程。
Adjacent = [[0, 10, 5, Inf, 8],
            [10, 0, 3, 1, Inf],
            [5, 3, 0, 9, 2],
            [Inf, 1, 9, 0, 6],
            [8, Inf, 2, 6, 0]]

Src, Dst, N = 0, 4, 5
def dijstra(adj, src, dst, n):
    dist = [Inf] * n#初始化为inf无穷大
    dist[src] = 0  #起始点到起始点距离为0
    vst = [0] * n  # 记录已经确定的顶点

    prev = [0]*n
    while True:
        now = -1
        for u in range(n):#找到dist最小且vst=0的点作为起点
            if not vst[u] and (now == -1 or dist[u] < dist[now]):
                now = u
        print('====now:', now)
        if now == -1:#now未被更新,即表示所有顶点都被使用过,算法结束
            break
        for v in range(n):#遍历当前起点now能到达的所有点
            if dist[v] > dist[now] + adj[now][v]:#如果dist[v]大于dist[now] + adj[now][v] 则更新
                dist[v] = dist[now] + adj[now][v]
                # prev[v] = now
            print('==dist:', dist)
        #     print('==prev:', prev)
        # assert 1==0
        vst[now] = 1#当前起点now已被使用过,vst[now]=1
    print('===dist:', dist)

    print('==dist[dst]:', dist[dst])
    return dist
res = dijstra(Adjacent, Src, Dst, N)
print('res:', res)

参考:

https://blog.csdn.net/weixin_43093481/article/details/82702176


本文链接: http://www.dtmao.cc/news_show_50412.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?