1

Написал алгоритм Дейкстры для ориентированного графа. Суть именного этого примера в том, что он находит наиболее вероятный успешный путь (т.е указаны вероятности поэтому используется умножение). Не проходит условие на 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))
1
  • Исправьте название вопроса. Это не ошибка в алгоритме Дейкстры, это ошибка в вашей реализации алгоритма Дейкстры.
    – passant
    17 окт 2019 в 20:30

1 ответ 1

1

Я правильно понял, что вы не суммируете веса, а множите? Тогда вы получите ерунду, алгоритм предназначен не для этого. Но если вы возьмете логарифмы весов (ваших вероятностей) со знаком минус, вспомните, что

  1. Вероятности не превышают 1
  2. Сумма логарифмов представляет собой логарифм произведения аргументов
  3. Условия для работы алгоритма Дейкстры

и немного подумаете - то поймете, что с весами

введите сюда описание изображения

алгоритм Дейкстры даст вам искомое...

0

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.