Мне было интересно, для алгоритма dijkstra и prim, что происходит, когда они выбирают между более чем одной вершиной, и есть несколько вершин с одинаковым весом.алгоритм dijkstra/prima ... немного помогает?
Например
Example Image http://img688.imageshack.us/img688/7613/exampleu.jpg
Это не имеет значения. Обычно галстук будет разбит каким-то произвольным образом, как тот, который сначала был добавлен в очередь приоритетов.
Целью Dijkstra является найти a кратчайший путь. Если вы хотите найти все самые короткие пути, вам необходимо будет беспокоиться о связях.
Исправьте меня, если я ошибаюсь, но ваш график не имеет альтернативных путей для применения алгоритма Дейкстры.
Да, не для праймов .. но может быть dijkstra's Начиная с вершины a и предполагая, что он только что обновлен b и c, сначала он перейдет к вершине c, а затем обновит вес для вершин d и вершины e. Теперь вершина e имеет вес 5, а также вершина b. Как он выбирает, какой из них следует перейти к следующему? mathmike вы говорите, что это случайный? спасибо – bfpri
Алгоритмы Dijkstra расширяют (или «расслабляют») все края от касаний, но не расширенный узел (или «серый» узел) с наименьшей стоимостью.
Если два узла имеет одинаковую стоимость, ну ... это просто случайный :)
Там может быть несколько MSTS, и каким-либо произвольные правила tiebreaking вы используете может дать вам другую, но она все равно быть MST.
Например, вы можете представить себе треугольник A-B-C, где все веса ребер являются едиными. В этом случае три MST, и все они минимальны.
То же самое касается Dijkstra и кратчайшего пути, охватывающего дерево - могут быть несколько кратчайших связующих деревьев.
Начиная с вершины a и предполагая, что он просто обновлен b и c, сначала он перейдет к вершине c, а затем обновит вес для вершин d и вершины e. Теперь вершина e имеет вес 5, а также вершина b. Как он выбирает, какой из них следует перейти к следующему? mathmike вы говорите, что это случайный? спасибо – bfpri
Я не математика, но я говорю, что это не имеет значения, поэтому вы можете сделать это случайным, если хотите. – Larry
alright thanks ... – bfpri
Начиная с вершины a и предполагая, что он просто обновлен b и c, сначала он перейдет к вершине c, а затем обновит вес для вершин d и вершины e. Теперь вершина e имеет вес 5, а также вершина b. Как он выбирает, какой из них следует перейти к следующему? mathmike вы говорите, что это случайный? спасибо – bfpri
Да, это по сути случайное. – mathmike
«случайный», вероятно, не является тем словом, которое вы хотите использовать в контексте компьютерной науки - это обычно означает «бросок кости» случайным образом. Варианты, которые вы разрешаете здесь, являются «произвольными» - любой возможный метод выбора между связанными значениями хорош. –