Skip to main content
 首页 » 编程设计

python之使用 Dijkstra 计算目的地之间的最短路线,字典帮助。 (Python)

2025年05月04日10EasonJim

我怎样才能像他们在这里所做的那样将值添加到字典:How to implement Dijkstra algorithm with Python (solved with all explanations) ? ?

我正在尝试创建一个程序,该程序将使用 Dijkstras 算法计算出目的地之间的最短路线,请参见下面的代码。

它目前接受邮政编码并在名为“geocodes”的列表中返回经度和纬度。我仍然需要以某种方式计算出每个地理编码之间的差异,然后将其添加到字典中。从那里我将能够从链接中实现代码。

如果有人能帮助我,我将不胜感激。

import urllib.request 
 
userinput = "" 
postcodes = [] 
geocodes = [] 
 
while userinput != ("q"): 
    print ("Enter postcode, Or q to finish") 
    postcode = input() 
    if postcode == "q" : 
        break 
    postcodes.append(postcode) 
    print (postcodes) 
 
for each in postcodes: 
    geocode = [] 
    core_string = 'http://uk-postcodes.com/postcode/' + each + '.xml' 
    response = urllib.request.urlopen(core_string) 
    html = response.read() 
    ##print(type(html)) 
    ##print(html) 
    raw_html = str(html)  
    ##print(raw_html) 
    ##print(raw_html.find("lat")) 
    latStartPoint = raw_html.find("<lat>")+5 
    latEndPoint = raw_html.find("</lat>")-1 
    lonStartPoint = raw_html.find("<lng>")+5 
    lonEndPoint = raw_html.find("</lng>")-1 
    lat = (raw_html[latStartPoint:latEndPoint]) 
    lon = (raw_html[lonStartPoint:lonEndPoint]) 
    geocode.append(lat) 
    geocode.append(lon) 
    geocodes.append(geocode) 

请您参考如下方法:

所以你已经构建了两个“平行”列表 postcodes 和 geocodes —— 其中后者的项目是 2-item 字符串 —— 你想要一个字典的字典以距离为最终值,对每个级别的键进行邮政编码。

对吗?

然后,唉,真的没有任何捷径......这是一个二次循环。

result = {p: {} for p in postcodes} 
joint_list = list(zip(postcodes, geocodes)) 
for i, (p, g) in enumerate(joint_list): 
    g = [float(x) for x in g] 
    for j in range(i+1, len(joint_list)): 
        op, og = joint_list[j] 
        og = [float(x) for x in og] 
        dist = distance(g, og) 
        result[p][op] = result[op][p] = dist 

当然在哪里

import math 
def distance(g1, g2): 
    return math.hypot(g1[0]-g2[0], g1[1]-g2[1])