Я только начал изучать алгоритм для графов, а точнее - алгоритм Флойда-Уоршалла. Глядя в википедию на алгоритм, измененный для обеспечения возможности восстановления пути, я заметил, что он сохраняет промежуточный узел вместо более логичного (на мой взгляд) способа - сохранения следующего прыжка. Более того, в учебнике путь сохраняется предпоследним узлом. Зачем сохранять путь таким образом?
Почему Флойд-Уоршалл странным образом помнит путь?
Ответы (1)
Нет никакого «следующего прыжка». Проблема заключается в хранении в компактном виде информации, достаточной для восстановления кратчайшего пути из i в j для любой комбинации узлов i и j. Предположим, что последнее ребро кратчайшего пути от i до j1 равно (k,j1), а последнее ребро кратчайшего пути от i до j2 равно (k,j2). Что бы вы сохранили в качестве «следующего прыжка» для узла k?
С другой стороны, предположим, что k — вершина с наивысшим индексом как на пути от i до j1, так и от i до j2. Оба кратчайших пути могут быть восстановлены рекурсивно с учетом информации, которую хранит алгоритм. Одним из них будет кратчайший путь от i до k, за которым следует кратчайший путь от k до j1. Другой будет кратчайшим путем из i в k, за которым следует кратчайший путь из k в j2. Сохранения одного узла на пути для каждой комбинации i,j достаточно, чтобы восстановить любой из кратчайших путей.
person
Patricia Shanahan
schedule
08.11.2013
Я знаю, что хранения одного узла достаточно. Рассмотрим кратчайший путь от 2 до 3 следующий:
2 -> 4 -> 6 -> 9 -> 5 -> 3 по алгоритму в википедии вы сохраните 9, по учебнику - 5. У меня вопрос: почему не 4?
- person elyashiv; 09.11.2013
