Посоветуйте с мат-формализмом алгоритма.

[MGM]

mihaild в сообщении #1598682 писал(а):

MGM в сообщении #1598662 писал(а):

что в результате работы такого обобщенного алгоритма , все вершины с минимальным расстоянием до какой-то конкретной корневой вершины, представляют собой связанный подграф

Вы имеете в виду, что если мы зафиксировали набор корневых вершин $v_1, \ldots, v_k$, то вершины, расстояние от которых до $v_i$ меньше, чем расстояние от них же до всех остальных корневых вершин, образуют связный подграф?
Это по сложности выглядит как среднего уровня сложности задача для начального курса по алгоритмам. Я не знаю обычаев в Вашей области, но вообще не выглядит как достаточно сложный результат.

Учился на кафедре Оптики физ-фака, все, чему меня учили по программированию на Алголе забыл к моменту выпуска. Сейчас уже не помню, была ли у нас дисциплина под названием Теория Множеств. Поэтому не представляю, на что способен студент мех-мата или ВМК. Более того, если вершина имеет равные расстояния до двух или более корневых вершин, то некоторые алгоритмы вполне могут выдать сементацию, где все вершины, обозначенные как ближайшие к корневой вершине n могут не образовывать связанного графа. Например, алгоритм, на который я вам дал ссылку (точнее на его мультикорневое рассширение), мало того, что требует значительно больших вычислительных затрат (так как перебирает все вершины при кажой итерации), так еще и дробит сементы, которые по идее должны быть связаны. А я ведь считал (примерно, как вы), что при полной релаксации подобного алгоритма, такого быть не должно. Более того, на каком-то шаге итерации этот алгоритм изолировал некоторые вершины от реально ближайшей. А значит алгоритм неточный. Хотя на первый взгляд он тоже похож на алгоритм Ф-Б. То есть перевод алгоритма Ф-Б к мультикорневому варианту не совсем тривиальная задача. ИМХО.

-- Пт июн 23, 2023 18:18:50 --

mihaild в сообщении #1598682 писал(а):

Но время $O(|E| \log |V|)$ даёт алгоритм Дейкстры с бинарной кучей, который опять же рассказывают первокурсникам (я пытался рассказывать и с фибоначчиевой кучей, но это была плохая идея).

А не поделитесь ссылкой на оба примера? Я вошел в возраст, когда решать подобные задачки доставлет удовольствие. А не желание найти какую-то корысть.

[mihaild]

MGM в сообщении #1598879 писал(а):

Более того, если вершина имеет равные расстояния до двух или более корневых вершин, то некоторые алгоритмы вполне могут выдать сементацию, где все вершины, обозначенные как ближайшие к корневой вершине n могут не образовывать связанного графа

"Ближайшие к корневой вершине" - это вершины, расстояние от которых до данной корневой вершины не больше, чем до любой другой, или что-то другое? Если это, то при положительных весах неважно, к какой из корневых вершин приписывать вершину, от который до нескольких разных корневых расстояние одинаковое.

MGM в сообщении #1598879 писал(а):

То есть перевод алгоритма Ф-Б к мультикорневому варианту не совсем тривиальная задача

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

[MGM]

mihaild в сообщении #1598888 писал(а):

MGM в сообщении #1598879 писал(а):

То есть перевод алгоритма Ф-Б к мультикорневому варианту не совсем тривиальная задача

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

Для меня это тоже очевидное утверждение. Если исходный алгоритм делает все правильно. Но это надо доказать. И в первую очередь формально, с привлечением понятия обратный путь и пр. А это многим и не надо.
На Матане некоторые доказательства мы выводили сами. В контексте предмета это часто тривиальная задача. Но ее постановка не всегда тривиальная.

Кстати о тривиальности. Алгоритм Дейкстры, например, с моей точки зрения достаточно трудно расширить до мультицентровой модели. И тем более до состояния связанности.
Если у вас число центров с нулевым расстоянием сравнимо с числом вершин (1000 против 100 000) то число операций будет просто неподьемным. Вы будете вынуждены создать тысячу карт расстояний от каждого центра до какждой вершины. Что как минимум в 1000 раз медлненнее, чем мой алгоритм, похожий (с точностью до терминологии) на ускоренный алгоритм Ф-Б.
А потом неизвестно как эти карты сводить к связанным подграфам. Когда вы одновременно вычисляете расстояние до ближайшего центра, и одновременно слтавите метку принадлежности к конкретному центру, можно доказать, что такой "лейблинг" образует связанные области. И совсем другое, когда вы имеете разные карты, где расстояния до двух и более корневых вершин одинаково. И что делать?
Я прочитал 4 объяснения алгоритма Дейкстры - могу сказать честно - совершенно непонятно, что хотели сказать автогры топиков на эту тему. И только у одного автора получилось объяснить мне суть, после того, как он привел доказательство в пару строк, что результат - минимальное расстояние.

[mihaild]

MGM в сообщении #1599137 писал(а):

Если исходный алгоритм делает все правильно

В смысле правильно находит кратчайшее расстояние?

MGM в сообщении #1599137 писал(а):

Алгоритм Дейкстры, например, с моей точки зрения достаточно трудно расширить до мультицентровой модели

Просто при инициализации объявить расстояние до всех стартовых вершин нулевым. Дальше как обычно.
Кроме того, задача с несколькими стартовыми вершинами сводится к задаче с одной стартовой вершиной простейшей предобработкой: склеиваем все стартовые вершины в одну, расстояние от которой до какой-нибудь другой равно минимуму расстояний от стартовых вершин до этой другой.

MGM в сообщении #1599137 писал(а):

И тем более до состояния связанности

MGM в сообщении #1599137 писал(а):

И совсем другое, когда вы имеете разные карты, где расстояния до двух и более корневых вершин одинаково.

Я не очень понимаю, в чем проблема.
Пусть у нас есть граф с положительными весами. Пусть в этом графе выбрано несколько вершин, называемых центром. Пусть в каждой вершине написан какой-нибудь из ближайших к ней центров. Утверждение: подграф, образованный вершинами, в которых написан один и тот же центр, связен.
Вам какие-то еще требования нужны?

MGM в сообщении #1599137 писал(а):

Я прочитал 4 объяснения алгоритма Дейкстры - могу сказать честно - совершенно непонятно, что хотели сказать автогры топиков на эту тему.

Это известная проблема, классические алгоритмы очень любят объяснять люди, сами их не понимающие. Алгоритм Дейкстры строго и подробно разобран у Кормена ("Алгоритмы: построение и анализ") и у Дасгупты ("Алгоритмы", объяснение чуть отличается от классического - алгоритм Дейкстры рассматривается как обобщение BFS).