图算法|Dijkstra算法python实现

栏目: Python · 发布时间: 6年前

内容简介:图算法|Dijkstra算法python实现

01

Dijkstra算法的理论部分

关于Dijkstra算法的原理部分,请参考之前的推送:

图算法|Dijkstra最短路径算法

Dijkstra算法总结如下:

1. 此算法是计算从入度为0的起始点开始的单源最短路径算法,它能计算从源点到图中任何一点的最短路径,假定起始点为A

2. 选取一个中心点center,是S集合中的最后一个元素,注意起始点到这个点的最短距离已经计算出来,并存储在dist字典中了。

3. 因为已经求出了从A->center的最短路径,所以每次迭代只需要找出center->{有关系的节点nodei}的最短距离,如果两者的和小于dist(A->nodei),则找到一条更短的路径。

02

代码实现

"""

Dijkstra algorithm

graphdict={"A":[("B",6),("C",3)], "B":[("C",2),("D",5)],"C":[("B",2),("D",3),("E",4)],\

"D":[("B",5),("C",3),("E",2),("F",3)],"E":[("C",4),("D",2),("F",5)],"F":[("D",3),"(E",5)]})

assert: start node must be zero in-degree

"""

def Dijkstra(startNode, endNode, graphdict=None):

S=[startNode]

V=[]

for node in graphdict.keys():

if node !=startNode:

V.append(node)

#distance dict from startNode

dist={}

for node in V:

dist[node]=float('Inf')

while len(V)>0:

center = S[-1] # get final node for S as the new center node

minval = ("None",float("Inf"))

for node,d in graphdict[center]:

if node not in V:

continue

#following is the key logic.If S length is bigger than 1,need to get the final ele of S, which is the center point in current

#iterator, and distance between start node and center node is startToCenterDist; d is distance between node

# among out-degree for center point; dist[node] is previous distance to start node, possibly Inf or a updated value

# so if startToCenterDist+d is less than dist[node], then it shows we find a shorter distance.

if len(S)==1:

dist[node] = d

else:

startToCenterDist = dist[center]

if startToCenterDist + d < dist[node]:

dist[node] = startToCenterDist + d

#this is the method to find a new center node and

# it's the minimum distance among out-degree nodes for center node

if d < minval[1]:

minval = (node,d)

V.remove(minval[0])

S.append(minval[0]) # append node with min val

return dist

03

测试

图算法|Dijkstra算法 <a href='https://www.codercto.com/topics/20097.html'>python</a> 实现

求出以上图中,从A到各个节点的最短路径:

shortestRoad = Dijkstra ("A","F",graphdict={"A":[("B",6),("C",3)], "B":[("C",2),("D",5)],\

"C":[("B",2),("D",3),("E",4)],\

"D":[("B",5),("C",3),("E",2),("F",3)],\

"E":[("C",4),("D",2),("F",5)],"F":[("D",3),("E",5)]})

mystr = "shortest distance from A begins to "

for key,shortest in shortestRoad.items():

print(mystr+ str(key) +" is: " + str(shortest) )

打印结果如下:

shortest distance from A begins to B is: 5
shortest distance from A begins to C is: 3
shortest distance from A begins to D is: 6
shortest distance from A begins to E is: 7
shortest distance from A begins to F is: 9

点击阅读原文,去我的github库下载代码。


以上所述就是小编给大家介绍的《图算法|Dijkstra算法python实现》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

统计学习方法

统计学习方法

李航 / 清华大学出版社 / 2012-3 / 38.00元

详细介绍支持向量机、Boosting、最大熵、条件随机场等十个统计学习方法。一起来看看 《统计学习方法》 这本书的介绍吧!

SHA 加密
SHA 加密

SHA 加密工具

Markdown 在线编辑器
Markdown 在线编辑器

Markdown 在线编辑器

RGB CMYK 转换工具
RGB CMYK 转换工具

RGB CMYK 互转工具