алгоритм Дейкстра / Прима ... немного помочь?

Question

Меня интересовал алгоритм Дейкстры и Прима, что происходит, когда они выбирают между несколькими вершинами, к которым нужно перейти, и существует более одной вершины с одинаковым весом.

Например

Пример изображения http://img688.imageshack.us/img688/7613/exampleu.jpg

Answer 1

Может быть несколько MST, и какие бы произвольные правила разрыва связи вы ни использовали, у вас может быть другое, но это все равно будет MST.

Например, вы можете представить треугольник ABC, где всеВес ребер один.В этом случае существует три MST, и все они минимальны.

То же самое относится к Дейкстре и остовному дереву кратчайшего пути - может быть несколько остовных деревьев кратчайшего пути.

Answer 2

Это не имеет значения. Обычно связь будет разорвана каким-либо произвольным образом, например, какой узел был добавлен в приоритетную очередь первым.

Цель Дейкстры - найти кратчайший путь. Если вы хотите найти всех кратчайших путей, вам придется беспокоиться о связях.

Answer 3

Алгоритмы Дейкстры расширяют (или «ослабляют») все ребра от прикосновения, но не расширенного узла (или «серого» узла) с наименьшей стоимостью.

Если два узла имеют одинаковую стоимость, ну ... это просто случайно:)

Answer 4

Поправьте меня, если я ошибаюсь, но у вашего графа нет альтернативных путей для применения алгоритма Дейкстры.