Имеется произвольный неориентированный граф, из любого узла в соседние может распространяться сигнал. Время перехода сигнала в соседние узлы всегда равно 1 вне зависимости от количества связей. Требуется определить минимально необходимое время для распространения сигнала во все узлы. Начинать можем с любого узла.
Кто подскажет более менее оптимальный алгоритм?

Давай на примерах
https://upload.wikimedia.org/wikipedia/commons/thumb/7/7d/Star_graphs.svg/718px-Star_graphs.svg.png
Для таких графов каково минимальное время?

(0) Дискретная математика.
Алгоритмов туча, выбирай любой: волновой, Дейкстры, Форда-Беллмана...

(1) 1

(2) Дейкстры реализовывал, оказался недостаточно оптимальным. Это задачка с одного сайта, там онлайн проверка решения

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

Для задачи в шапке:
Волна из каждой вершины плюс контроль, посещали ли мы эту вершину до этого (можно сделать как массив bool[N], где N количество вершин). Сложность N^3. Смотрите, уложитесь или нет. Если граф без циклов, то можно можно посмотреть и другие алгоритмы.

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

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

(6) попробую

(6) сейчас почитал, по сути я и делал волну, а не Дейкстры. Но не уложился во время.