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

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

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

瀏覽:45日期: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 編程
相關文章:
主站蜘蛛池模板: Q361F全焊接球阀,200X减压稳压阀,ZJHP气动单座调节阀-上海戎钛 | 环氧乙烷灭菌器_压力蒸汽灭菌器_低温等离子过氧化氢灭菌器 _低温蒸汽甲醛灭菌器_清洗工作站_医用干燥柜_灭菌耗材-环氧乙烷灭菌器_脉动真空压力蒸汽灭菌器_低温等离子灭菌设备_河南省三强医疗器械有限责任公司 | 飞行者联盟-飞机模拟机_无人机_低空经济_航空技术交流平台 | 无压烧结银_有压烧结银_导电银胶_导电油墨_导电胶-善仁(浙江)新材料 | 合肥活动房_安徽活动板房_集成打包箱房厂家-安徽玉强钢结构集成房屋有限公司 | 柴油发电机组_柴油发电机_发电机组价格-江苏凯晨电力设备有限公司 | 国际学校_国际学校哪个好_国际课程学校-国际学校择校网 | 中式装修设计_室内中式装修_【云臻轩】中式设计机构 | 仓储货架_南京货架_钢制托盘_仓储笼_隔离网_环球零件盒_诺力液压车_货架-南京一品仓储设备制造公司 | 反渗透水处理设备|工业零排放|水厂设备|软化水设备|海南净水设备--海南水处理设备厂家 | 冻干机(冷冻干燥机)_小型|实验型|食品真空冷冻干燥机-松源 | 哲力实业_专注汽车涂料汽车漆研发生产_汽车漆|修补油漆品牌厂家 长沙一级消防工程公司_智能化弱电_机电安装_亮化工程专业施工承包_湖南公共安全工程有限公司 | 济南品牌设计-济南品牌策划-即合品牌策划设计-山东即合官网 | 食品机械专用传感器-落料放大器-低价接近开关-菲德自控技术(天津)有限公司 | 商用绞肉机-熟肉切片机-冻肉切丁机-猪肉开条机 - 广州市正盈机械设备有限公司 | 无线联网门锁|校园联网门锁|学校智能门锁|公租房智能门锁|保障房管理系统-KEENZY中科易安 | 匀胶机旋涂仪-声扫显微镜-工业水浸超声-安赛斯(北京)科技有限公司 | 加盟店-品牌招商加盟-创业项目商机平台 | 不锈钢螺丝 - 六角螺丝厂家 - 不锈钢紧固件 - 万千紧固件--紧固件一站式采购 | 钛板_钛管_钛棒_钛盘管-无锡市盛钛科技有限公司 | 运动木地板_体育木地板_篮球馆木地板_舞台木地板-实木运动地板厂家 | 尊享蟹太太美味,大闸蟹礼卡|礼券|礼盒在线预订-蟹太太官网 | 欧必特空气能-商用空气能热水工程,空气能热水器,超低温空气源热泵生产厂家-湖南欧必特空气能公司 | 防火门-专业生产甲级不锈钢钢质防火门厂家资质齐全-广东恒磊安防设备有限公司 | 不锈钢水管-不锈钢燃气管-卫生级不锈钢管件-不锈钢食品级水管-广东双兴新材料集团有限公司 | 中药二氧化硫测定仪,食品二氧化硫测定仪|俊腾百科 | 润滑脂-高温润滑脂-轴承润滑脂-食品级润滑油-索科润滑油脂厂家 | 一体化净水器_一体化净水设备_一体化水处理设备-江苏旭浩鑫环保科技有限公司 | 短信通106短信接口验证码接口群发平台_国际短信接口验证码接口群发平台-速度网络有限公司 | 微波萃取合成仪-电热消解器价格-北京安合美诚科学仪器有限公司 | 海外整合营销-独立站营销-社交媒体运营_广州甲壳虫跨境网络服务 焊管生产线_焊管机组_轧辊模具_焊管设备_焊管设备厂家_石家庄翔昱机械 | 济南玻璃安装_济南玻璃门_济南感应门_济南玻璃隔断_济南玻璃门维修_济南镜片安装_济南肯德基门_济南高隔间-济南凯轩鹏宇玻璃有限公司 | 无菌实验室规划装修设计-一体化实验室承包-北京洁净净化工程建设施工-北京航天科恩实验室装备工程技术有限公司 | 【直乐】河北石家庄脊柱侧弯医院_治疗椎间盘突出哪家医院好_骨科脊柱外科专业医院_治疗抽动症/关节病骨伤权威医院|排行-直乐矫形中医医院 | 领先的大模型技术与应用公司-中关村科金 | 南京技嘉环保科技有限公司-杀菌除臭剂|污水|垃圾|厕所|橡胶厂|化工厂|铸造厂除臭剂 | 石油/泥浆/不锈钢防腐/砂泵/抽砂泵/砂砾泵/吸砂泵/压滤机泵 - 专业石油环保专用泵厂家 | 搪瓷反应釜厂家,淄博搪瓷反应釜-淄博卓耀| 智能气瓶柜(大型气瓶储存柜)百科 | 火锅加盟_四川成都火锅店加盟_中国火锅连锁品牌十强_朝天门火锅【官网】 | 北京印刷厂_北京印刷_北京印刷公司_北京印刷厂家_北京东爵盛世印刷有限公司 |