python实现Dijkstra算法的最短路径问题
作者:程序媛0420 发布时间:2023-05-18 23:22:15
迪杰斯特拉(Dijkstra)算法主要是针对没有负值的有向图,求解其中的单一起点到其他顶点的最短路径算法。
1 算法原理
迪杰斯特拉(Dijkstra)算法是一个按照路径长度递增的次序产生的最短路径算法。下图为带权值的有向图,作为程序中的实验数据。
其中,带权值的有向图采用邻接矩阵graph来进行存储,在计算中就是采用n*n的二维数组来进行存储,v0-v5表示数组的索引编号0-5,二维数组的值表示节点之间的权值,若两个节点不能通行,比如,v0->v1不能通行,那么graph[0,1]=+∞ (采用计算机中最大正整数来进行表示)。那如何求解从v0每个v节点的最短路径长度呢?
首先,引进一个辅助数组cost,它的每个值cost[i]表示当前所找到的从起始点v0到终点vi的最短路径的权值(长度花费),该数组的初态为:若从v0到vi有弧,则cost[i]为弧上的权值,否则置cost[i]为+∞。
显然,长度为:cost[j]=Min_i(graph[0,i] | v_i in V)的路径就是从v0出发的长度最短的一条最短路径。此路径为(v_0,v_j) ,那么下次长度次短的路径必定是弧(v_0,v_i)上的权值cost[i](v_i in V),或者是cost[k](v_k in S)和弧(v_k,v_i)的权值之和。其中V:待求解最短路径的节点j集合;S:已求解最短路径的节点集合。
2 算法流程
根据上面的算法原理分析,下面描述算法的实现流程。
初始化:初始化辅助数组cost,从v0出发到图上其余节点v的初始权值为:cost[i]=graph[0,i] | v_i in V ;初始化待求节点S集合,它的初始状态为始点,V集合,全部节点-始节点。
选择节点v_j ,使得cost[j]=Min ( cost[i] | v_i in V -S ) ,v_j 就是当前求的一条从v0出发的最短路径的终点,修改S集合,使得 S=S + V_j ,修改集合V = V - V_j。
修改从v0出发到节点V-S上任一顶点 v_k 可达的最短路径,若cost[j]+graph[j,k]<cost[k] ,则修改cost[k]为:cost[k]=cost[j]+graph[j,k] 。
重复操作2,3步骤,直到求解集合V中的所有节点为止。
其中最短路径的存储采用一个path整数数组,path[i]的值记录vi的前一个节点的索引,通过path一直追溯到起点,就可以找到从vi到起始节点的最短路径。比如起始节点索引为0,若path[3]=4, path[4]=0;那么节点v2的最短路径为,v0->v4->v3。
3 算法实现
采用python语言对第2节中的算法流程进行实现,关键代码如下。
3.1 最短路径代码
#!/bin/python
# -*- coding:utf-8 -*-
def dijkstra(graph, startIndex, path, cost, max):
"""
求解各节点最短路径,获取path,和cost数组,
path[i] 表示vi节点的前继节点索引,一直追溯到起点。
cost[i] 表示vi节点的花费
"""
lenth = len(graph)
v = [0] * lenth
# 初始化 path,cost,V
for i in range(lenth):
if i == startIndex:
v[startIndex] = 1
else:
cost[i] = graph[startIndex][i]
path[i] = (startIndex if (cost[i] < max) else -1)
# print v, cost, path
for i in range(1, lenth):
minCost = max
curNode = -1
for w in range(lenth):
if v[w] == 0 and cost[w] < minCost:
minCost = cost[w]
curNode = w
# for 获取最小权值的节点
if curNode == -1: break
# 剩下都是不可通行的节点,跳出循环
v[curNode] = 1
for w in range(lenth):
if v[w] == 0 and (graph[curNode][w] + cost[curNode] < cost[w]):
cost[w] = graph[curNode][w] + cost[curNode] # 更新权值
path[w] = curNode # 更新路径
# for 更新其他节点的权值(距离)和路径
return path
if __name__ == '__main__':
max = 2147483647
graph = [
[max, max, 10, max, 30, 100],
[max, max, 5, max, max, max],
[max, max, max, 50, max, max],
[max, max, max, max, max, 10],
[max, max, max, 20, max, 60],
[max, max, max, max, max, max],
]
path = [0] * 6
cost = [0] * 6
print dijkstra(graph, 0, path, cost, max)
4 运行结果
[0, -1, 0, 4, 0, 3]
来源:https://www.cnblogs.com/mayunting/p/10426705.html
猜你喜欢
- 下列代码都是以自己的项目实例讲述的,相关的文本内容很少,主要说明全在代码注释中自制图形验证码这里所说的图形验证码都是自制的图形,通过画布、画
- 是否曾经有过这样的经历:把一个元素置于另一个元素之上,而希望下面的那个元素成为可点击的?现在,利用css的pointer-events属性即
- 像在下拉菜单中选择省、市这样的操作,我一直用ASP来创建生成列表函数,把它们保存在一个Include文件中,用的时候就加载。这样做确实有个不
- Python tcp socket编程详解初学脚本语言Python,测试可用的tcp通讯程序:服务器:#!/usr/bin/env pyth
- 大家做网站,特别是自己写的代码,常常担心被一些黑客入侵服务器,从而导致网站代码被盗,给自己带来一些损失。那么我们怎么样做,就算黑客盗了你的代
- 使用Access数据库生成申报数据与读入数据的实例方法:示例:Sub Mwrite()On Error GoTo thiserrDim rs
- 本文实例为大家分享了JS实现拖动模糊框特效的具体代码,供大家参考,具体内容如下需求:在图片上拖动按钮,图片蒙层慢慢覆盖,当蒙层边缘碰到左右下
- CSS与JS紧密配合,为我们的页面增添了很多别致的效果。为了达到某种特殊的效果我们需要用Javascript动态的去更改某一个标签的CSS属
- 前言很多人会使用postman工具,或者熟悉python,但不一定会使用python来编写测试用例脚本,postman里面可以完整的将pyt
- 本人已经在运维行业工作了将近十年,我最早接触Linux是在大二的样子,那时候只追求易懂,所以就选择了Ubuntu作为学习、使用的对象,它简单
- tensor计算三通道均值今天用pytorch处理图像时,涉及到了计算均值的问题,整理一下解决思路。第一种思路tensor转换为numpy再
- 实体有五种预定义的XML实体,HTML编码者应该熟悉。XML文档中的字符&、<、>、"和'被分别表示为
- asp过滤留言中脏话的代码例子<!--#include file="../conn/dbconn1.asp"--&
- 本文实例介绍了使用javascript来经验表单数据的方法,如:校验是否为英文,校验是否为数字及校验IP地址等: &l
- MySQL、SQL Server和mSQL都是绝佳的SQL工具,可惜,在ASP的环境下你却用不着它们来创建实用的SQL语句。不过,你可以利用
- scriptlet的使用jsp页面中分三种scriptlet:第一种:<% %> 可以在里面写java的代码。定义java变量以
- php代码实现读取文件头判断文件类型,支持图片、rar、exe等后缀。案例:<?php $filename = "11.jp
- 1、给滚动条换色 好多网站的滚动条不是系统默认的灰色,而是一些红色、蓝色的,请问这是如何做的?答:这个很好实现,插入下面的代码:<&n
- 项目地址https://github.com/jonssonyan...开发工具 python 3.7.9pycharm 2019.3.5
- 今天在群里,熊猫君提议整理一个帖子,一方面为初学者提供一个入门指南,另一方面也象借此和已经在从事这个行业进行一点交流。下面是我从事这个行当多