реализация dijkstra в python - вывод не всегда корректен - PullRequest
Новая
       11

реализация dijkstra в python - вывод не всегда корректен

0 голосов
/ 07 мая 2018

Я сделал эту реализацию алгоритма Дейкстры кратчайших путей с приоритетом dict, основанным на куче.У него есть следующие методы: smalllest () - возвращает только самый маленький ключ из dict, который имеет наименьшее значение.pop_smallest () возвращает наименьший ключ с наименьшим значением в куче, а также извлекает его из запроса кучи.Я тестировал код на некоторых тестах на github, и некоторые тесты верны, некоторые нет.Я видел еще много реализаций для этого алгоритма, но я хотел бы исправить мои, прежде чем я увижу других, которые лучше моих.

Я новичок, у вас может быть сформированный глаз, чтобы определить, что не такв моем коде.С уважением, Редактировать: я не знаю, разрешено ли мне публиковать ссылки на другие сайты, но этот сайт содержит тесты, которые я использовал: https://github.com/beaunus/stanford-algs/tree/master/testCases/course2/assignment2Dijkstra Контекст заключается в том, что эта реализация является частью задания для Coursera Standfordкласс о графиках.Задание должно было вычислить расстояния до 7-го узла, 35-го узла и т. Д.).Если некоторые из них неправильны, очевидно, что-то пошло не так в коде.Для большей ясности тест input_random_10_16 выдает разные ответы.Не все расстояния правильные.

  • Выводы моей реализации: [878, 405, 785, 534, 909, 328, 708, 957, 830, 911]
  • Правильный ответ: [588, 405,675, 521, 909, 328, 418, 957, 830, 839]

Некоторые расстояния правильные, некоторые нет.

РЕДАКТИРОВАТЬ: Я наконец переделал другую реализацию, которая прошлавсе тесты.Это реализация кучи.Я также хотел сделать наивную реализацию, которая не использовала кучу.Я искал в Интернете различные наивные реализации и обнаружил несколько неправильных результатов, что и в этой реализации.Как это возможно?Хорошая реализация, также размещенная на github, которая работала для многих людей, когда использовалась на моем графике, превзошла эти неверные результаты.

def dijkstra(graph, s):
    processed = set([s])
    vertexes = set([])
    distances = {}
    ans = []
    heap = priority_dict()
    for i in graph:
        vertexes.add(i)
        distances[i] = 0
        if i not in processed:
            heap[i] = float('inf')
    while processed != vertexes:
        for i in processed:
            neigh = graph[i]
            for j in heap:
                if j in neigh:
                    score = distances[i] + graph[i][j]
                    if score < heap[j]:
                        heap[j] = score
        smallest_value = heap[heap.smallest()]
        smallest_key = heap.pop_smallest()
        processed.add(smallest_key)
        distances[smallest_key] = smallest_value
        for j in graph[smallest_key]:
            if j in heap:
                old_val = heap[j]
                new_val = min(old_val, distances[smallest_key] + graph[smallest_key][j])
                heap[j] = new_val
    list_ = [7,37,59,82,99,115,133,165,188,197]
    for i in list_:
        ans.append(distances[i])
    return ans

1 Ответ

0 голосов
/ 07 мая 2018

Некоторые части алгоритма кажутся неправильными: На самом деле источник не должен быть уже обработан в начале. Это должна быть единственная вершина с расстоянием 0. Затем она будет выбрана в качестве первого маленького ключа. Поэтому начало цикла while, где вы вычисляете все результаты, больше не понадобится. Единственная часть, которая должна будет выполнить обновления, - это обновление расстояний соседей наименьшего_ключа в конце цикла. 

def dijkstra(graph, s):
    processed = set([])
    vertexes = set([])
    distances = {}
    ans = []
    heap = priority_dict()
    for i in graph:
        vertexes.add(i)
        distances[i] = 0
        if i != s:
            heap[i] = float('inf')
        else:
            heap[i] = 0 
    while processed != vertexes:
        smallest_value = heap[heap.smallest()]
        smallest_key = heap.pop_smallest()
        processed.add(smallest_key)
        distances[smallest_key] = smallest_value
        for j in graph[smallest_key]:
            if j in heap:
                old_val = heap[j]
                new_val = min(old_val, distances[smallest_key] + graph[smallest_key][j])
                heap[j] = new_val
    list_ = [7,37,59,82,99,115,133,165,188,197]
    for i in list_:
        ans.append(distances[i])
    return ans
...