У меня есть алгоритм Беллмана-Форда на Python. Никак не соображу, как восстановить и вывести путь. __AdjList - список смежности. __amount - размерность графа.
def BellmanFord(self, src):
INF = 10 ** 9
dist = dict.fromkeys(self.__AdjList.keys(), INF)
dist[src] = 0
visited = dict.fromkeys(self.__AdjList.keys(), INF)
for i in range(self.__amount - 1):
for u in self.__AdjList.keys():
for v in self.__AdjList[u].keys():
w = self.__AdjList[u][v]
if dist[u] != INF and int(dist[u]) + int(w) < int(dist[v]):
dist[v] = int(dist[u]) + int(w)
for u in self.__AdjList.keys():
for v in self.__AdjList[u].keys():
w = self.__AdjList[u][v]
# if dist[u] != float("Inf") and dist[u] + w < dist[v]:
if dist[u] != INF and int(dist[u]) + int(w) < int(dist[v]):
return 'Graph contains negative weight cycle'
for x in list(dist.keys()):
if x in dist and dist[x] == INF:
dist.pop(x)
return dist
Edited:
def BellmanFord(self, src, b):
INF = 10 ** 9
dist = dict.fromkeys(self.__AdjList.keys(), INF)
dist[src] = 0
pred = list()
for i in range(self.__amount - 1):
for u in self.__AdjList.keys():
for v in self.__AdjList[u].keys():
w = self.__AdjList[u][v]
if dist[u] != INF and int(dist[u]) + int(w) < int(dist[v]):
dist[v] = int(dist[u]) + int(w)
pred[v] = u
for u in self.__AdjList.keys():
for v in self.__AdjList[u].keys():
w = self.__AdjList[u][v]
# if dist[u] != float("Inf") and dist[u] + w < dist[v]:
if dist[u] != INF and int(dist[u]) + int(w) < int(dist[v]):
return 'Graph contains negative weight cycle'
for x in list(dist.keys()):
if x in dist and dist[x] == INF:
dist.pop(x)
path = [b]
temp = b
while temp != src:
temp = pred[temp]
path.append(temp)
print(path[::-1])