597400 |
Помогите с Турбо Паскалем, пожалуйста! 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
|
|
|
|
|
ET |
Re: Помогите с Турбо Паскалем, пожалуйста! 13.10.2008, 05:34 |
|
08/05/08 600
|
Пр чем тут турбо-паскаль и форматы файлов? Сомневаюсь, что кто-то вам все на блюдечке принесет. Даже боюсь, как бы меня модеры за мой пост не побили.
Когда-то на 1м курсе была у меня другая задача, для нее придумал тогда нормальный нерекурсивный быстрый алгоритм определения кратчайшего расстояния в графе, хочу посоветовать.
С каждой вершиной связывай число : (расстояние, до первой из вершин, между которыми надо найти кратчайший путь) Заполняй его так: на первом шаге первой вершине пиши 0, все остальным - бесконечность.
Далее на каждом следующем шаге это число делай минимум того, что есть и минимум по всем соседям то, что у них плюс расстояние до соседей. (в данной задаче расстояние до соседей всегда равно 1 если я правильно понял ) Делай так до тех пор, пока все значения не стабилизируются.
Когда все стабилизируется смотри на число, записаное во 2й вершине(между которыми надо найти путь). Если оно бесконечность, то не судьба туда попасть. А если конкретное число - то это число ходов, за которые попасть можно по кратчайшему пути, по записаным числам в вершинах графа этот путь несложно восстанавливается
|
|
|
|
|
Sрy |
17.10.2008, 10:51 |
|
16/09/07 34
|
Есть несколько алгоритмов для нахождения кратчайшего пути в графе. Алгоритм Дейкстры очень неплохой. Советую почитать Кормена, там много информации про графы.
Правда, в Дейкстре нужно очередь с приоритетами использовать - если препод придирается к времени работы алгоритма, то придётся эту бинарную кучу реализовывать. И применяется, насколько я помню, для взвешенных графов.
А для тех, где расстояния либо 1, либо 0, то поиск в ширину должен помочь.
|
|
|
|
|
|
Страница 1 из 1
|
[ Сообщений: 3 ] |
|
Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы