Я пытаюсь решить проблему, когда мне нужно найти кратчайший путь от источника к источнику. Итак, мне предоставлен список смежности L, где L[i] представляет вершины, связанные с i. Каждая вершина может рассматриваться как железнодорожная станция. Стоимость перемещения из одной вершины в другую равна нулю. Это потому, что мы предполагаем, что существует беговая дорожка между каждой станцией.
Нам также предоставляют вершину, которая представляет станцию рядом с нашим домом, назовите ее h, не в списке смежности, но она связана с каждой вершиной в графе. Нам также предоставляется список кортежей C, где C[i][0] - это стоимость поездки от дома до тренировочной станции i, а C[i][1] - это стоимость возвращения со станции i на нашу h. То, что мы хотим сделать, - это найти самый дешевый маршрут, с помощью которого мы путешествуем от станции x к вершине на графике, бежим к другой станции (или нескольким станциям) и затем возвращаемся обратно к x (не со станции, которую мы впервые используется). Я думал об использовании Dijkstra с моим текущим подходом, похожим на:
def dijkstra(C, L):
def min_distance(dj, distance):
min_so_far = float('inf')
for k, v in distance.items():
if not dj[k] and v <= min_so_far:
min_so_far = v
min_ind = k
return min_ind
nodes = len(L)
# dj will denote whether we've explored a node before or not
dj = dict((node, False) for node in nodes)
# Make provisional distances the cost of going from `h` to a particular
# node
distance = dict((node, C[node][0]) for node in nodes)
parent = dict((node, None) for node in nodes)
for _ in len(nodes):
u = min_distance(dj, distance)
dj[u] = True
for v in L[u]:
if not dj[v] and distance[u] + C[v][1] < distance[v]:
distance[v] = distance[u] + C[v][1]
parent[v] = u
return min(distance, key=distance.get)
Однако, это похоже на наивный подход к этой проблеме и не вычисляет правильное расстояние. У кого-нибудь есть другие идеи о том, как подойти к этой проблеме?