алгоритм dijkstra/prim … немного справки?
Я задавался вопросом для алгоритма dijkstra и prim, что происходит, когда они принимают решение больше чем между одной вершиной перейти в, и существует больше чем одна вершина с тем же весом.
Например,
Изображение в качестве примера http://img688.imageshack.us/img688/7613/exampleu.jpg
4 ответа
Может быть несколько MST, и какие бы произвольные правила разрешения конфликтов вы не использовали, может дать вам другое, но это все равно будет MST.
Например, вы можете представить треугольник A-B-C, в котором веса всех ребер равны единице. В данном случае есть три MST, и все они минимальные.
То же самое касается Дейкстры и остовного дерева кратчайшего пути - может быть несколько остовных деревьев кратчайшего пути.
Неважно. Обычно связь прерывается произвольным образом, например, какой узел был добавлен в приоритетную очередь первым.
Цель Дейкстры - найти кратчайший путь. Если вы хотите найти все кратчайшие пути, вам придется беспокоиться о связях.
Поправьте меня, если я ошибаюсь, но на вашем графике нет альтернативных путей для применения алгоритма Дейкстры.
Алгоритмы Дейкстры расширяют (или «расслабляют») все ребра от касания, но не расширяют узел (или «серый» узел) с наименьшими затратами.
Если два узла имеют одинаковую стоимость, ну ... это просто случайность :)