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

[Эдгар]

исходные данные даны матрицей :

1 5 6 9 10 20 21 22 33
2 3 4 11 12 * * * *
3 1 5 19 20 25 * * *
******************
40 26 27 29 31 37 * * *



надо чтобы прокладывало маршрут(односторонний) из начальной точки(например 1) в конечную(например18) и его выводило (например 1-5-20-13-18), у каждой точки есть от 0 до 10 точек в которые можно из нее попасть но в одну сторону( из этих точек обратно нельзя) и условие что в цепочке не меньше 3х точек и не больше 5





я так понял надо применить Алгоритм Дейкстры для поиска кратчайшего пути в графе:
for k:=1 to N do
for i:=1 to N do
for j:=1 to N do
d[i,j]:=min(d[i,j], d[i,k]+d[k,j]);

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

[Эдгар]

тут помогают или нет?)
из точки 1 можно попасть в 5 ,6 9, 10,20,21,22,23
из 2 в 3,4,11 или 12 соответственно, и так далее это пояснение к исходникам

уверен что задачка примитивна и решается на раз два помогите пожалуйста)

[IgorGO]

случается иногда

[IgorGO]

Уважаемый Эдгар, я не обнаружил точной постановки задачи в Вашем изложении, поэтому решал задачу поставленную самому себе по мотивам Вашей.

Итак, в моей задаче в качестве исходных взято 100 точек. В нижней таблице случайным образом написано из какой точки в какую есть путь. Предполагается, что из точки с меньшим порядковым номером можно попасть только в точку с большим номером. Количество тропинок из каждой точки равно 5 (можно до 10, нарисована сетка). Если в Вашей задаче число тропинок произвольное, необходимо написать реальные пути, а у тех точек, а где их мало - дополнить "фиктивными путями" до точки 100, которой нет на плане.

Над кнопкой "старт" пишем номер начальной, конечной точки графа, и максимальное количество переходов. Жмем "старт". Видим последовательности переходов. Для поочередной визуализации графов достаточно написать номер графа под кнопкой "старт". Условное форматирование закрасит нужные ячейки.

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

Собственно там 20 строк алгоритма, и 10 строк подготовки к расчетам.

[Эдгар]

Супер!!! Это то что надо!!! Прога супер!!! только еще один маленький нюанс ... у меня точки это строки текстовые... можно точку 1 сопоставить с одним словом, 2- с другим и так далее? и результат что бы писало И словами...?=) ОГРОМНОЕ СПАСИБО!!!!

[IgorGO]

Внимание:
- теперь вместо цифр можно использовать названия точек (любые строки)
- для каждой точки может быть указано произвольное количество путей (связей с другими точками)
- обрабатывается 100 строк с данными
- рекурсивная процедура очень чувствительна к количеству обрабатываемых данных.

[Эдгар]

- теперь вместо цифр можно использовать названия точек (любые строки)

не понял как это сделать)))и хотелось бы иметь возможность увидеть результат в виде цепочки названий точек...(а может даже и задавать начальную и конечную точку по их названиям...)



- рекурсивная процедура очень чувствительна к количеству обрабатываемых данных.
не совсем понял о чем Вы излагаетесь=)

[Эдгар]

часто происходит ошибка "28" и ссылается на эту строку
If Cells(RowP(TAr(s).t), TAr(s).l + 2) = "" Then

[Эдгар]

- рекурсивная процедура очень чувствительна к количеству обрабатываемых данных.

кажись я понял что это значит=)))

[Эдгар]

это сообщение не смотреть=) (не знаю как удалить....)