Question

Практическая работа Проект «Поход в магазин» Сегодня день рождения Айдоса. К нему придут в гости его друзья Айдос должен сделать покупки в двух магазинах, расположен Расстояние от дома Айдоса до первого магазина составляет а м ных рядом с его домом, чтобы встретить и угостить своих друзей до второго магазина - b м, а расстояние между двумя магазинам составляет с м. Помогите Айдосу найти кратчайший путь от дом до двух магазинов и обратно (рис. 2).
ПОЖАЛУЙСТА СРОЧЧЧЧНОООО ДАЮ 20 БАЛЛЛООООВ​

Answer 1

import heapq

def dijkstra(graph, start):

visited = set()

dist = {vertex: float('inf') for vertex in graph}

dist[start] = 0

prev = {vertex: None for vertex in graph}

pq = [(0, start)]

while pq:

(min_dist, curr_vertex) = heapq.heappop(pq)

if curr_vertex in visited:

continue

visited.add(curr_vertex)

for neighbor, weight in graph[curr_vertex].items():

distance = dist[curr_vertex] + weight

if distance < dist[neighbor]:

dist[neighbor] = distance

prev[neighbor] = curr_vertex

heapq.heappush(pq, (distance, neighbor))

return dist, prev

# Граф, заданный в условии задачи

graph = {

'дом': {'магазин1': a, 'магазин2': b},

'магазин1': {'дом': a, 'магазин2': c},

'магазин2': {'дом': b, 'магазин1': c}

}

# Находим кратчайший путь от дома до магазина1

dist1, prev1 = dijkstra(graph, 'дом')

# Находим кратчайший путь от дома до магазина2

dist2, prev2 = dijkstra(graph, 'дом')

# Находим кратчайший путь между магазинами

dist12, prev12 = dijkstra(graph, 'магазин1')

# Составляем общий кратчайший путь

path1 = []

vertex = 'магазин1'

while vertex:

path1.append(vertex)

vertex = prev1[vertex]

path1.reverse()

path2 = []

vertex = 'магазин2'

while vertex:

path2.append(vertex)

vertex = prev2[vertex]

path2.reverse()

path12 = []

vertex = 'магазин2'

while vertex != 'магазин1':

path12.append(vertex)

vertex = prev12[vertex]

path12.reverse()

shortest_path = path1 + path12 + path2