TIL#122の最短の経路を求めます
最短距離のボールを習いました:)
import copy
departure = 'home'
destination = 'school'
# 한 장소에서 다른 장소로의 거리 가중치를 담은 landscpae 딕셔너리를 만들어 준다
landscape = {
'home': {'hair_shop': 5, 'super_market': 10, 'english_academy': 9},
'hair_shop': {'home': 5, 'super_market': 3, 'bank': 11},
'super_market': {'hair_shop': 3, 'home': 10, 'english_academy': 7, 'restaurant': 3},
'english_academy': {'home': 9, 'super_market': 7, 'school': 12},
'restaurant': {'super_market': 3, 'bank': 4},
'bank': {'hair_shop': 11, 'restaurant': 4, 'english_academy': 7, 'school': 2},
'school': {'bank': 2, 'english_academy': 12}
}
routing = dict()
for place in landscape.keys():
routing[place] = {'shortest_distance': 0, 'route': [], 'visited': 0}
def visit_place(visit):
routing[visit]['visited'] = 1
for to_go, between_distance in landscape[visit].items():
to_distance = routing[visit]['shortest_distance'] + between_distance
if (routing[to_go]['shortest_distance'] >= to_distance) or not routing[to_go]['route']:
routing[to_go]['shortest_distance'] = to_distance
routing[to_go]['route'] = copy.deepcopy(routing[visit]['route'])
routing[to_go]['route'].append(visit)
visit_place(departure)
while 1:
minimum_distance = max(routing.values(), key=lambda x: x['shortest_distance'])['shortest_distance']
to_visit = ''
for name, search in routing.items():
if 0 < search['shortest_distance'] <= minimum_distance and not search['visited']:
minimum_distance = search['shortest_distance']
to_visit = name
if to_visit == '':
break
visit_place(to_visit)
print(routing)
print('route: ', routing[destination]['route'])
print('shortest_distance: ', routing[destination]['shortest_distance'])
理解しましたが、まだまだ難しかったです.まだまだ勉強が必要みたいです:)# output
{'home': {'shortest_distance': 10, 'route': ['home', 'hair_shop'], 'visited': 1}, 'hair_shop': {'shortest_distance': 5, 'route': ['home'], 'visited': 1}, 'super_market': {'shortest_distance': 8, 'route': ['home', 'hair_shop'], 'visited': 1}, 'english_academy': {'shortest_distance': 9, 'route': ['home'], 'visited': 1}, 'restaurant': {'shortest_distance': 11, 'route': ['home', 'hair_shop', 'super_market'], 'visited': 1}, 'bank': {'shortest_distance': 15, 'route': ['home', 'hair_shop', 'super_market', 'restaurant'], 'visited': 1}, 'school': {'shortest_distance': 17, 'route': ['home', 'hair_shop', 'super_market', 'restaurant', 'bank'], 'visited': 1}}
route: ['home', 'hair_shop', 'super_market', 'restaurant', 'bank']
shortest_distance: 17
Reference
この問題について(TIL#122の最短の経路を求めます), 我々は、より多くの情報をここで見つけました https://velog.io/@dnpxm387/TIL-최단경로-구하기テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol