Delphi, алгоритма Беллмана-Шимбела (графы, вычисления кратчайшего пути)

[ZX Spectrum-128]

Что-то я запутался. Завтра почитаю заново алгоритм. В вики вроде как немножко по другому алгоритм описан.

[ogamilait]

Сообщение от ZX Spectrum-128

Что-то я запутался. Завтра почитаю заново алгоритм. В вики вроде как немножко по другому алгоритм описан.

Есть такое но мне он чото не нравитса, у меня есть алгоритм в doc файле правда на "Українській".
http://vk.com/doc22419499_238672532?...7ce71d660fdc00

[ZX Spectrum-128]

Я почитал еще раз в вики про алгоритм, не совпадает он с тем, как вы описываете. На украинском я все равно не пойму. Мне на английском проще.

[ogamilait]

Сообщение от ZX Spectrum-128

Я почитал еще раз в вики про алгоритм, не совпадает он с тем, как вы описываете. На украинском я все равно не пойму. Мне на английском проще.

Печально, может быть я не так понял его на лекции

[ZX Spectrum-128]

Ну вот описание:
Про главную диагональ нет ничего.

Алгоритм Шимбелла позволяет находить минимальные (максимальные)
пути между вершинами, состоящие из заданного количества ребер.
Введем специальные операции над элементами матрицы:
1) Операция умножения двух величин а и b при возведении матрицы в
степень соответствует их алгебраической сумме:
2) Операция сложения двух величин а и b заменяется выбором из этих
величин минимального (максимального) элемента:
Нули при этом игнорируются. Минимальный (максимальный) элемент
выбирается из ненулевых элементов. Ноль в результате операции может быть
получен лишь тогда, когда все элементы нулевые.
С помощью этих операций длины минимальных (максимальных) путей
определяются возведением в степень весовой матрицы Ω.

[ogamilait]

Сообщение от ZX Spectrum-128

Ну вот описание:
Про главную диагональ нет ничего.

Я уже и сам запутался немного...

Переведу на русский, может это хоть как то прояснит что нужно в итоге:
В основе алгоритма Беллмана-Шимбела лежит очевидное соотношение (14.5).
С (14.5) получаем, (14.6)
Используя (14.6) можем последовательно формировать матрицы (14.7).
Очевидно, что все вышеуказанные матрицы являются симметричными.
Элементы последовательности (14.7) вычисляются до тех пор, пока при некотором d не будут получены две равные соседние матрицы.

Тоесть пока последняя матрица не будет равна предыдущей.

[ZX Spectrum-128]

А есть подробное описание на русском? Какая-то редкая модификация алгоритма Беллмана?

[ogamilait]

Сообщение от ZX Spectrum-128

А есть подробное описание на русском? Какая-то редкая модификация алгоритма Беллмана?

Нашол страница 2:
http://archive.nbuv.gov.ua/portal/so..._4_2/45-47.pdf

[ogamilait]

Вот еще полное описания:
http://vk.com/doc22419499_241956097?...d24a83fed307b2
294 ст.

[ZX Spectrum-128]

Скачал.
Хорошо, я посмотрю, как комп появится.