|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
19.12.2010, 01:39 | #1 |
Пользователь
Регистрация: 30.11.2010
Сообщений: 29
|
длина пути между двумя вершинами в графе
В неориентированном графе требуется найти длину кратчайшего пути между двумя вершинами.
Входные данные Во входном файле INPUT.TXT записано сначала число N – количество вершин в графе (1 ≤ N ≤ 100). Затем записана матрица смежности (0 обозначает отсутствие ребра, 1 – наличие ребра). Затем записаны номера двух вершин – начальной и конечной. Выходные данные В выходной файл OUTPUT.TXT выведите длину кратчайшего пути. Если пути не существует, выведите одно число – 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 Решать не обязательно.. Просто объясните алгоритм.. |
19.12.2010, 10:42 | #2 |
Пользователь
Регистрация: 03.11.2010
Сообщений: 95
|
нужно использовать алгоритм Уоршалла для нахождения матрицы минимальных длин путей.
предположим, что A - это матрица смежности графа. Заменим все нулевые элементы A на "бесконечность" или на некоторое "очень большое число", которое обозначим через B. в коде это примерно так: Код:
|
19.12.2010, 10:55 | #3 |
Пользователь
Регистрация: 30.11.2010
Сообщений: 29
|
А что такое MaxNodes?
|
19.12.2010, 10:59 | #4 |
Пользователь
Регистрация: 30.11.2010
Сообщений: 29
|
А если через волновой алгоритм?:
Код:
|
19.12.2010, 11:15 | #5 | |
Пользователь
Регистрация: 30.11.2010
Сообщений: 29
|
Цитата:
|
|
19.12.2010, 17:54 | #6 |
Пользователь
Регистрация: 03.11.2010
Сообщений: 95
|
как не подходит - очень даже подходит. С помощью этой матрицы уже можно определить пути из любой вершины в любую, например если матрица такая
1 2 0 3 4 1 2 0 2 то минимальный путь из одной вершины в другую - это 1 (из 2 в 3) - это если не считать петли |
Опции темы | Поиск в этой теме |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Заданная длина пути | Ubersetzer | Помощь студентам | 0 | 16.11.2010 16:44 |
Кратчайший путь между двум вершинами | Gapro | Общие вопросы C/C++ | 4 | 04.11.2010 20:24 |
кратчайшие расстояния между вершинами | pum-pum-pum | Помощь студентам | 1 | 07.01.2010 11:30 |
Кратчайшее расстояние между всеми вершинами | ooooch | Помощь студентам | 5 | 15.11.2009 15:36 |