Ошибка в реализации алгоритма Дейкстры - PullRequest
Новая
       12

Ошибка в реализации алгоритма Дейкстры

0 голосов
/ 18 октября 2019

Помощь с алгоритмом Дейкстры. Суть задачи: нужно найти наиболее вероятный путь. Здесь используется умножение вероятностей. Ввод: 100, 9900, 1, 100 (Количество вершин, количество дуг, начальная и конечная вершины) 1, 2, 0.3 (начальная, конечная и вероятность прохождения пути) ...

Мой результат: 

35, 35, 3, 54, 98, 100 (most likely successful path)
0.9577 (probability of passage).

Правильный результат: 

1, 92, 35, 3, 54, 98, 100
0.9577

Я думаю, что эта часть кода работает неправильно (построение кратчайшего пути): 

 while (i!=0):
            for j in range(end, -1, -1):
                if (ves[i]!=0.0 and round(weight[i] / ves[i],6) == weight[j] and i<=test):
                    result.append(j+1)
                    test=j
            i -= 1

Весь код: 

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],6) > weight[i] and i<end+1):
                weight[i] = round(weight[ID_min_weight] * matrix[ID_min_weight][i],6)
                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],6) == 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))
...