2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Помогите с Турбо Паскалем, пожалуйста!
Сообщение12.10.2008, 19:15 


12/10/08
22
Путь

В неориентированном графе требуется найти минимальный путь между
двумя вершинами.

Входные данные
Во входном файле записано сначала число N - количество вершин в графе
(1<=N<=100). Затем записана матрица смежности (0 обозначает отсутствие ребра,
1 - наличие ребра). Затем записаны номера двух вершин - начальной и конечной.

Выходные данные
В выходной файл выведите сначала L - длину пути (количество ребер, которые
нужно пройти). А затем выведите L+1 число - вершины в порядке следования
вдоль этого пути.
Если пути не существует, выведите одно число -1.

Пример входного файла
5
0 1 0 0 1
1 0 1 0 0
0 1 0 0 0
0 0 0 0 0
1 0 0 0 0
3 5

Пример выходного файла
3
3 2 1 5

 Профиль  
                  
 
 Re: Помогите с Турбо Паскалем, пожалуйста!
Сообщение13.10.2008, 05:34 


08/05/08
593
Пр чем тут турбо-паскаль и форматы файлов? Сомневаюсь, что кто-то вам все на блюдечке принесет. Даже боюсь, как бы меня модеры за мой пост не побили.
Когда-то на 1м курсе была у меня другая задача, для нее придумал тогда нормальный нерекурсивный быстрый алгоритм определения кратчайшего расстояния в графе, хочу посоветовать.
С каждой вершиной связывай число : (расстояние, до первой из вершин, между которыми надо найти кратчайший путь) Заполняй его так: на первом шаге первой вершине пиши 0, все остальным - бесконечность.
Далее на каждом следующем шаге это число делай минимум того, что есть и минимум по всем соседям то, что у них плюс расстояние до соседей. (в данной задаче расстояние до соседей всегда равно 1 если я правильно понял ) Делай так до тех пор, пока все значения не стабилизируются.
Когда все стабилизируется смотри на число, записаное во 2й вершине(между которыми надо найти путь). Если оно бесконечность, то не судьба туда попасть. А если конкретное число - то это число ходов, за которые попасть можно по кратчайшему пути, по записаным числам в вершинах графа этот путь несложно восстанавливается

 Профиль  
                  
 
 
Сообщение17.10.2008, 10:51 


16/09/07
34
Есть несколько алгоритмов для нахождения кратчайшего пути в графе. Алгоритм Дейкстры очень неплохой. Советую почитать Кормена, там много информации про графы.
Правда, в Дейкстре нужно очередь с приоритетами использовать - если препод придирается к времени работы алгоритма, то придётся эту бинарную кучу реализовывать. И применяется, насколько я помню, для взвешенных графов.
А для тех, где расстояния либо 1, либо 0, то поиск в ширину должен помочь.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 3 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group