电脑知识|欧美黑人一区二区三区|软件|欧美黑人一级爽快片淫片高清|系统|欧美黑人狂野猛交老妇|数据库|服务器|编程开发|网络运营|知识问答|技术教程文章 - 好吧啦网

您的位置:首頁技術文章
文章詳情頁

Python實現迪杰斯特拉算法過程解析

瀏覽:42日期:2022-07-10 17:23:15

一、 迪杰斯特拉算法思想

Dijkstra算法主要針對的是有向圖的單元最短路徑問題,且不能出現權值為負的情況!Dijkstra算法類似于貪心算法,其應用根本在于最短路徑的最優子結構性質。

最短路徑的最優子結構性質:

如果P(i,j)={Vi…Vk…Vs…Vj}是從頂點i到j的最短路徑,k和s是這條路徑上的一個中間頂點,那么P(k,s)必定是從k到s的最短路徑。

證明:

假設P(i,j)={Vi…Vk…Vs…Vj}是從頂點i到j的最短路徑,則有P(i,j)=P(i,k)+P(k,s)+P(s,j)。而P(k,s)不是從k到s的最短距離,那么必定存在另一條從k到s的最短路徑P(k,s),那么P(i,j)=P(i,k)+P(k,s)+P(s,j)<P(i,j)。則與P(i,j)是從i到j的最短路徑相矛盾。因此該性質得證。

因此,Dijkstra算法描述如下:

Dijikstra算法描述如下:

假設存在G=<V,E>,源頂點為V0,S={V0},distance[i]記錄V0到i的最短距離,matrix[i][j]記錄從i到j的邊的權值,即兩點之間的距離。

1)從V-S中選擇使dist[i]值最小的頂點i,將i加入到U中;

2)更新與i直接相鄰頂點的dist值。dist[j]=min{dist[j],dist[i]+matrix[i][j]}

3)直到S=V,所有頂點都包含進來了,算法停止。

二、 具體操作步驟

根據其算法思想,確立操作步驟如下:

(1) 初始時,S只包含起點s;U包含除s外的其他頂點,且U中頂點的距離為'起點s到該頂點的距離'[例如,U中頂點v的距離為(s,v)的長度,然后s和v不相鄰,則v的距離為∞]。

(2) 從U中選出'距離最短的頂點k',并將頂點k加入到S中;同時,從U中移除頂點k。

(3) 更新U中各個頂點到起點s的距離。之所以更新U中頂點的距離,是由于上一步中確定了k是求出最短路徑的頂點,從而可以利用k來更新其它頂點的距離;例如,(s,v)的距離可能大于(s,k)+(k,v)的距離。

(4) 重復步驟(2)和(3),直到遍歷完所有頂點。

三、代碼

def dijkstra(s, used, cost, distance, n): distance[s] = 0 while True: # v在這里相當于是一個哨兵,對包含起點s做統一處理! v = -1 # 從未使用過的頂點中選擇一個距離最小的頂點 for u in range(n): if not used[u] and (v == -1 or distance[u] < distance[v]):v = u if v == -1: # 說明所有頂點都維護到S中了! break # 將選定的頂點加入到S中, 同時進行距離更新 used[v] = True # 更新U中各個頂點到起點s的距離。之所以更新U中頂點的距離,是由于上一步中確定了k是求出最短路徑的頂點,從而可以利用k來更新其它頂點的距離;例如,(s,v)的距離可能大于(s,k)+(k,v)的距離。 for u in range(n): distance[u] = min(distance[u], distance[v] + cost[v][u]) return distancen, m, T = map(int, input().split())# 標記數組:used[v]值為False說明改頂點還沒有訪問過,在S中,否則在U中!used = [False for _ in range(n)]# 距離數組:distance[i]表示從源點s到i的最短距離,distance[s]=0distance = [float(’inf’) for _ in range(n)]# cost[u][v]表示邊e=(u,v)的權值,不存在時設為INFcost = [[float(’inf’) for _ in range(n)] for _ in range(n)]for _ in range(m): e = list(map(int, input().split())) cost[e[0] - 1][e[1] - 1] = e[2]dis1 = dijkstra(0, used[:], cost, distance[:], n)d1 = dis1[-1]dis2 = dijkstra(n-1, used[:], cost, distance[:], n)d2 = dis2[0]print((d1+d2)*T)

以上就是本文的全部內容,希望對大家的學習有所幫助,也希望大家多多支持好吧啦網。

標簽: Python 編程
相關文章:
主站蜘蛛池模板: 螺旋绞龙叶片,螺旋输送机厂家,山东螺旋输送机-淄博长江机械制造有限公司 | 缠膜机|缠绕包装机|无纺布包装机-济南达伦特机械设备有限公司 | 天助网 - 中小企业全网推广平台_生态整合营销知名服务商_天助网采购优选 | 传爱自考网_传爱自学考试网| Dataforth隔离信号调理模块-信号放大模块-加速度振动传感器-北京康泰电子有限公司 | 智能风向风速仪,风速告警仪,数字温湿仪,综合气象仪(气象五要素)-上海风云气象仪器有限公司 | 深圳法律咨询【24小时在线】深圳律师咨询免费 | 百度关键词优化_网站优化_SEO价格 - 云无限好排名 | 电梯乘运质量测试仪_电梯安全评估测试仪-武汉懿之刻 | 冷热冲击试验箱_温度冲击试验箱价格_冷热冲击箱排名_林频厂家 | 连栋温室大棚建造厂家-智能玻璃温室-薄膜温室_青州市亿诚农业科技 | (中山|佛山|江门)环氧地坪漆,停车场地板漆,车库地板漆,聚氨酯地板漆-中山永旺地坪漆厂家 | 工业废水处理|污水处理厂|废水治理设备工程技术公司-苏州瑞美迪 今日娱乐圈——影视剧集_八卦娱乐_明星八卦_最新娱乐八卦新闻 | 硫化罐_蒸汽硫化罐_大型硫化罐-山东鑫泰鑫智能装备有限公司 | 济宁工业提升门|济宁电动防火门|济宁快速堆积门-济宁市统一电动门有限公司 | 板框压滤机-隔膜压滤机配件生产厂家-陕西华星佳洋装备制造有限公司 | 防爆型气象站_农业气象站_校园气象站_农业四情监测系统「山东万象环境科技有限公司」 | 心得体会网_心得体会格式范文模板 | 皮带机-带式输送机价格-固定式胶带机生产厂家-河南坤威机械 | 众品地板网-地板品牌招商_地板装修设计_地板门户的首选网络媒体。 | 大通天成企业资质代办_承装修试电力设施许可证_增值电信业务经营许可证_无人机运营合格证_广播电视节目制作许可证 | 代做标书-代写标书-专业标书文件编辑-「深圳卓越创兴公司」 | 山东商品混凝土搅拌楼-环保型搅拌站-拌合站-分体仓-搅拌机厂家-天宇 | 黄石东方妇产医院_黄石妇科医院哪家好_黄石无痛人流医院 | 耐磨陶瓷,耐磨陶瓷管道_厂家-淄博拓创陶瓷科技 | 铁艺,仿竹,竹节,护栏,围栏,篱笆,栅栏,栏杆,护栏网,网围栏,厂家 - 河北稳重金属丝网制品有限公司 山东太阳能路灯厂家-庭院灯生产厂家-济南晟启灯饰有限公司 | 车牌识别道闸_停车场收费系统_人脸识别考勤机_速通门闸机_充电桩厂家_中全清茂官网 | 实验室装修_实验室设计_实验室规划设计- 上海广建净化工程公司 | 粘度计,数显粘度计,指针旋转粘度计 | 免费分销系统 — 分销商城系统_分销小程序开发 -【微商来】 | 耐酸泵,耐酸泵厂家-淄博华舜耐腐蚀真空泵 | 紧急切断阀_气动切断阀_不锈钢阀门_截止阀_球阀_蝶阀_闸阀-上海上兆阀门制造有限公司 | 长沙网站建设制作「网站优化推广」-网页设计公司-速马科技官网 | 根系分析仪,大米外观品质检测仪,考种仪,藻类鉴定计数仪,叶面积仪,菌落计数仪,抑菌圈测量仪,抗生素效价测定仪,植物表型仪,冠层分析仪-杭州万深检测仪器网 | 标策网-专注公司商业知识服务、助力企业发展 | 滑板场地施工_极限运动场地设计_滑板公园建造_盐城天人极限运动场地建设有限公司 | 【中联邦】增稠剂_增稠粉_水性增稠剂_涂料增稠剂_工业增稠剂生产厂家 | 净化板-洁净板-净化板价格-净化板生产厂家-山东鸿星新材料科技股份有限公司 | 水冷式工业冷水机组_风冷式工业冷水机_水冷螺杆冷冻机组-深圳市普威机械设备有限公司 | 日本细胞免疫疗法_肿瘤免疫治疗_NK细胞疗法 - 免疫密码 | 小程序开发公司-小程序制作-微信小程序开发-小程序定制-咏熠软件 |