我有一个json文件,其中列出了位置和里程。还为dijkstra算法创建了一个函数,该函数包含3个参数。我已经加载了我的json文件,但是我在函数中使用了哪三个参数作为start-end和graph参数来显示最短路径
地点和距离的Json文件
{
"Western Governors University 4001 South 700 East, Salt Lake City, UT 84107": {
"International Peace Gardens 1060 Dalton Ave S": 7.2,
"Sugar House Park 1330 2100 S": 3.8,
"Taylorsville-Bennion Heritage City Gov Off 1488 4800 S": 11.0,
"Salt Lake City Division of Health Services 177 W Price Ave": 2.2,
"South Salt Lake Public Works 195 W Oakland Ave": 3.5,
"Salt Lake City Streets and Sanitation 2010 W 500 S": 10.9,
"Deker Lake 2300 Parkway Blvd": 8.6,
"Salt Lake City Ottinger Hall 233 Canyon Rd": 7.6,
"Columbus Library 2530 S 500 E": 2.8,
"Taylorsville City Hall 2600 Taylorsville Blvd": 6.4,
"South Salt Lake Police 2835 Main St": 3.2,
"Council Hall 300 State St": 7.6,
"Redwood Park 3060 Lester St": 5.2,
"Salt Lake County Mental Health 3148 S 1100 W": 4.4,
"Salt Lake County/United Police Dept 3365 S 900 W": 3.66112816434,
"West Valley Prosecutor 3575 W Valley Central Sta bus Loop": 7.6,
"Housing Auth. of Salt Lake County 3595 Main St": 2.0,
"Utah DMV Administrative Office 380 W 2880 S": 3.6,
"Third District Juvenile Court 410 S State St": 6.5,
"Cottonwood Regional Softball Complex 4300 S 1300 E": 1.9,
"Holiday City Office 4580 S 2300 E": 3.4,
"Murray City Museum 5025 State St": 2.4,
"Valley Regional Softball Complex 5100 South 2700 West": 6.4,
"City Center of Rock Springs 5383 South 900 East #104": 2.4,
"Rice Terrace Pavilion Park 600 E 900 South": 5.0,
"Wheeler Historic Farm 6351 South 900 East": 3.6
},
"International Peace Gardens 1060 Dalton Ave S": {
"Western Governors University 4001 South 700 East, Salt Lake City, UT 84107": 7.2,
"Sugar House Park 1330 2100 S": 7.1,
"Taylorsville-Bennion Heritage City Gov Off 1488 4800 S": 6.4,
"Salt Lake City Division of Health Services 177 W Price Ave": 6.0,
"South Salt Lake Public Works 195 W Oakland Ave": 4.8,
"Salt Lake City Streets and Sanitation 2010 W 500 S": 1.6,
"Deker Lake 2300 Parkway Blvd": 2.8,
"Salt Lake City Ottinger Hall 233 Canyon Rd": 4.8,
"Columbus Library 2530 S 500 E": 6.3,
"Taylorsville City Hall 2600 Taylorsville Blvd": 7.3,
"South Salt Lake Police 2835 Main St": 5.3,
"Council Hall 300 State St": 4.8,
"Redwood Park 3060 Lester St": 3.0,
"Salt Lake County Mental Health 3148 S 1100 W": 4.6,
"Salt Lake County/United Police Dept 3365 S 900 W": 4.5,
"West Valley Prosecutor 3575 W Valley Central Sta bus Loop": 7.4,
"Housing Auth. of Salt Lake County 3595 Main St": 6.0,
"Utah DMV Administrative Office 380 W 2880 S": 5.0,
"Third District Juvenile Court 410 S State St": 4.8,
"Cottonwood Regional Softball Complex 4300 S 1300 E": 9.5,
"Holiday City Office 4580 S 2300 E": 10.9,
"Murray City Museum 5025 State St": 8.3,
"Valley Regional Softball Complex 5100 South 2700 West": 6.9,
"City Center of Rock Springs 5383 South 900 East #104": 10.0,
"Rice Terrace Pavilion Park 600 E 900 South": 4.4,
"Wheeler Historic Farm 6351 South 900 East": 13.0
},
"Sugar House Park 1330 2100 S": {
"Western Governors University 4001 South 700 East, Salt Lake City, UT 84107": 3.8,
"International Peace Gardens 1060 Dalton Ave S": 7.1,
"Taylorsville-Bennion Heritage City Gov Off 1488 4800 S": 9.2,
"Salt Lake City Division of Health Services 177 W Price Ave": 4.4,
"South Salt Lake Public Works 195 W Oakland Ave": 2.8,
"Salt Lake City Streets and Sanitation 2010 W 500 S": 8.6,
"Deker Lake 2300 Parkway Blvd": 6.3,
"Salt Lake City Ottinger Hall 233 Canyon Rd": 5.3,
"Columbus Library 2530 S 500 E": 1.6,
"Taylorsville City Hall 2600 Taylorsville Blvd": 10.4,
"South Salt Lake Police 2835 Main St": 3.0,
"Council Hall 300 State St": 5.3,
"Redwood Park 3060 Lester St": 6.5,
"Salt Lake County Mental Health 3148 S 1100 W": 5.6,
"Salt Lake County/United Police Dept 3365 S 900 W": 5.8,
"West Valley Prosecutor 3575 W Valley Central Sta bus Loop": 5.7,
"Housing Auth. of Salt Lake County 3595 Main St": 4.1,
"Utah DMV Administrative Office 380 W 2880 S": 3.6,
"Third District Juvenile Court 410 S State St": 4.3,
"Cottonwood Regional Softball Complex 4300 S 1300 E": 3.3,
"Holiday City Office 4580 S 2300 E": 5.0,
"Murray City Museum 5025 State St": 6.1,
"Valley Regional Softball Complex 5100 South 2700 West": 9.7,
"City Center of Rock Springs 5383 South 900 East #104": 6.1,
"Rice Terrace Pavilion Park 600 E 900 South": 2.8,
"Wheeler Historic Farm 6351 South 900 East": 7.4
}
最短路径的算法函数
def dijkstrasShortestDistance(start, end, graph):
visited = chainingHashMap()
paths = list()
paths.append(([start], 0))
while len(paths) > 0:
nowPath = paths.pop()
finalItem = nowPath[0][-1]
hasVisited = visited.get(finalItem)[0]
if not hasVisited:
visited.insert(finalItem, True)
else:
continue
if finalItem == end:
return nowPath
nextTuple = graph.get(finalItem)
if not nextTuple[0]:
continue
nextNodes = nextTuple[1]
for nextNodes in nextNodes:
newPath = list(nowPath[0])
newPath.append(nextNodes[0])
newDistance = nowPath[1]
newDistance += nextNodes[1]
paths.append((newPath, newDistance))
paths = sorted(paths, key=lambda tuple_item: tuple_item[0])
return (list(), 0)
娱乐节目的主要部分
distance = load_json(os.path.join(mainDirectory, 'distanceTable.json'))
print(dijkstrasShortestDistance(not sure how to get info from json into here)
每个位置都是一个图节点。每个目的地表示一条边;以下距离是一个边值。首先,您有:
这涉及三个节点,每个位置一个;我们叫他们WGU,IPG,SHP。您还有两条带值(重量或成本)的边:
您必须迭代输入以构建图形。由于您可以方便地在dict中输入所有内容,我希望您可以从这里继续
相关问题 更多 >
编程相关推荐