Написал алгоритм Дейкстры для ориентированного графа. Суть именного этого примера в том, что он находит наиболее вероятный успешный путь (т.е указаны вероятности поэтому используется умножение). Не проходит условие на 100 вершин и 9900 дуг. При этом проходит 100 вершин и ~5000 дуг. Видимо что-то не учтено но я не могу найти что. Может по опыту сможет кто-то подсказать? Инпут выглядит так: 1 2 0.5 (начальная вершина - конечная вершина - вероятность) Вывод так: 1 2 4 6 (наибольшее вероятный успешный путь) 0.4444 (вероятность прохождения пути)
Заранее извиняюсь за криворукость.
def Dijkstra(N, S, matrix, end):
valid = [True] * N
weight = [0.01] * N
weight[S] = 1.0
ves=[0.0]*N
result=[]
for i in range(N):
min_weight = 0.0
ID_min_weight = 0.0
for i in range(len(weight)):
if valid[i] and weight[i] > min_weight:
min_weight = weight[i]
ID_min_weight = i
for i in range(N):
if (round(weight[ID_min_weight] * matrix[ID_min_weight][i],4) > weight[i] and i<end+1):
weight[i] = round(weight[ID_min_weight] * matrix[ID_min_weight][i],4)
ves[i]=matrix[ID_min_weight][i]
valid[ID_min_weight] = False
result.append(end + 1)
i = end
test = end
while (i!=0):
for j in range(end, -1, -1):
if (ves[i]!=0.0 and round(weight[i] / ves[i],4) == weight[j] and i<=test):
result.append(j+1)
test=j
i -= 1
result.reverse()
print (*result)
return round(weight[end],4)
str=[]
matrix2=[]
for i in input().split():
str.append(int(i))
N = str[0] # Количество вершин
M = str[1] # Количество дуг
begin = str[2] # Начальная вершина
end = str[3] # Конечная вершина
matrix = [[float (j) for j in input().split()] for i in range(M)]
for i in matrix:
if len(i)>3:
exit()
for i in range(N):
matrix2.append([])
for j in range(N):
matrix2[i].append(0.01)
for i in range(M):
matrix2[int(matrix[i][0]-1)][int(matrix[i][1]-1)] = matrix[i][2]
print(Dijkstra(N, begin-1, matrix2,end-1))