Нахождение кратчайшего пути на графе.

[Мария74]

Помогите с задачей на Delphi.Нахождение кратчайшего пути на графе.

[Мария74]

есть программа. но она не работает, помогите найти причину

[Utkin]

Мария это известная задача. Почитайте в инете алгоритм Дейкстры. Существуют еще много других варинатов, но они либо вариации либо сложней.

[Мария74]

Сообщение от Utkin

Мария это известная задача. Почитайте в инете алгоритм Дейкстры. Существуют еще много других варинатов, но они либо вариации либо сложней.

Я понимаю что это все давным давно известно. Попробовала решить после прочитанного в интернете. Запускается но работает не корректно. Поэтому и прошу помочь найти причину

[phomm]

Я бы помог, но от Вас надо
1. Полные данные на которых тестить программу и какой при этом должен быть результат.
2. Объясните общую логику алгоритма и программы. Я так понимаю, в гриде матрица смежности графа (правда она почему-то 4*4 а в коде 10*10 массив). Но пока сомнения насчет что вводить в эдтиы. Вводил граф такой: 4 точки, 1 соед с 3 и 4, 3 соед с 4 , 2 не соединена ни с кем (в гриде 6 единичек проставил, на 3 связи. с зеркалированием по гл. диаг.). Путь от 1 до 2 прога ничего не вывела, путь 1-3 прога вывела "1 3, длина:4512268"
Я теряюсь хоть как-то понять результат. Алгоритм пробежался глазами, но ввиду возможной там ошибки вникать не стал, ибо мне неизвестно как должен работать алгоритм, а тут ещё и он неправильно запрограммирован по идее..

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

[Мария74]

тестировала программу на вот таких данных:
0 1 1 1 0 0 0
1 0 0 0 0 0 0
1 0 0 1 0 0 1
1 0 1 0 0 1 0
0 0 0 0 0 1 1
0 0 0 1 1 0 1
0 0 1 0 1 1 0
из точки 1 в точку 5 должны попасть по пути 1 3 4 6 5
Вообще в сети нашла только этот алгоритм нахождения пути
пользовалась эти ресурсом http://prodelphi.ucoz.ru/index/poisk_puti/0-165?lyeosi
Откуда появляется длинна я не поняла. По идее длина должна задаваться с клавиатуры

[phomm]

Вот так исправил, проверьте, искать стал норм, и выводить длину пути, но только не всегда самый короткий путь... (по моим прикидкам должны быть более быстрые пути а он просто некий путь кажет). Также не знаю реализовано ли в том алгоритме поиск с учетом веса ребра графа.. было бы хорошо, но я даже не проверил, раз он по единичным весам некорректно ищет. Надо будет Вам пошагово прогнать программу и проверить всё.
Сейчас уже нет времени у меня, возможно потом.

Файлы просто замените и перезапустите проект в дельфи.

[Мария74]

Большое спасибо, а подскажите как реализовать графически этот алгоритм, с чего начать?

[phomm]

Научитесь, пожалуйста, ставить вопросы.
Что значит реализовать графически? Мы с Вами можем абсолютно по-разному понимать это, и если Вы хотите сразу работать в нужном направлении, то лучше очень чётко всё расписывать.

Начать можно с изучения свойств и методов класса Canvas , почти все учебные пособия по дельфи имеют главы по данной теме.

[_-Re@l-_]

Дейкстра не айс, алгоритм Форда-Беллмана рулит, даже по асимптотике ( O(n * m) против O(n^2) у Дейкстры), да плюс Дейкстра с отрицательными ребрами не работает. Да и в реализации Форд-Беллман гораздо проще И, по-моему, интуитивно понятней.
Читать тут