За последние 24 часа нас посетили 8707 программистов и 457 роботов. Сейчас ищут 128 программистов ...

Алгоритм Дейкстры

Тема в разделе "Решения, алгоритмы", создана пользователем Exort, 3 фев 2020.

  1. Exort

    Exort Активный пользователь

    С нами с:
    30 апр 2016
    Сообщения:
    100
    Симпатии:
    2
    Дорогие друзья, доброго времени суток.
    За ранее большое спасибо за ваше время.

    Изучаю алгоритм дейкстры, хочу понять, зачем нужен массив "parents"?
    Т.е. зачем вершине (узлу или точке, терминология очень размыта) знать, откуда я пришёл?

    В книге, а также многих мануалах учат инициализировать 4 массива:
    - graph (здесь всё понятно)
    - costs (вес вершин)
    - processed (пройденные вершины)
    - parents (не понимаю, зачем?)

    Пожалуйста, объясните, зачем он нужен? В теории роль этого массива не описана
     
  2. Sail

    Sail Активный пользователь

    С нами с:
    1 ноя 2016
    Сообщения:
    1.253
    Симпатии:
    281
    @Exort, чтобы не только знать длину кратчайшего пути, но и иметь возможность его восстановить.
     
    Exort нравится это.
  3. Exort

    Exort Активный пользователь

    С нами с:
    30 апр 2016
    Сообщения:
    100
    Симпатии:
    2
    т.е. чтобы знать путь от начального узла до конечного?
     
  4. Sail

    Sail Активный пользователь

    С нами с:
    1 ноя 2016
    Сообщения:
    1.253
    Симпатии:
    281
    Подробнее