Форум программистов, компьютерный форум, киберфорум
C# для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/5: Рейтинг темы: голосов - 5, средняя оценка - 5.00
1 / 1 / 1
Регистрация: 14.12.2015
Сообщений: 125
1

Работа с графом

13.12.2016, 09:28. Просмотров 848. Ответов 4
Метки нет (Все метки)


Написать программу, которая находит по заданным вершинам графа все пути между ними и определяет кратчайший путь. Сам граф представлен в виде матрицы смежности.
Нужен сам алгоритм поиска всех путей и поиска среди них кратчайшего.
Вот пример работы программы с такой матрицей смежности:
0, 12, 5, 0;
12, 0, 6, 20;
5, 6, 0, 7;
0, 20, 7, 0;
Далее пользователь выбирает 2 вершины, например 1 и 4, вывод программы будет таким:
Все пути:
1, 2, 3, 4
1, 2, 4
1, 3, 2, 4
1, 3, 4
Кратчайший путь:
1, 3, 4
Его длина:
12
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
13.12.2016, 09:28
Ответы с готовыми решениями:

Работа с неориентированным графом
Есть неориентированный граф 4х4, нужно составить алгоритм, который бы находил пути в которых...

Подскажите библиотеку для представления JSON блок схемой (графом)
Есть ли на wpf библиотека для десериализации JSON-а в блок схемы? Очень не хочется руками рисовать,...

Работа с графом
Здравствуйте, у меня такая проблема ,по матрице смежности (7x7) со случайными числами я получил...

Работа с Ориентированным графом
Дан орграф. После удаления произвольных вершин может произойти всё что угодно, вопрос таков: Для...

4
Злой няш
1949 / 1384 / 508
Регистрация: 05.04.2010
Сообщений: 2,627
13.12.2016, 09:34 2
Возьми тот код, который искал все пути и добавь в цикл поиск длины, а после цикла - проверку длины: если минимальная, запомни эту длину и путь.
0
1 / 1 / 1
Регистрация: 14.12.2015
Сообщений: 125
13.12.2016, 09:42  [ТС] 3
Я не совсем ещё разобрался, как тот код работает, было бы не плохо, если бы вы сейчас дополнили тот код и добавили комментариев.
Заранее большое спасибо.
0
Злой няш
1949 / 1384 / 508
Регистрация: 05.04.2010
Сообщений: 2,627
13.12.2016, 09:50 4
Цитата Сообщение от HomBro Посмотреть сообщение
если бы вы сейчас дополнили тот код
Не, мне лень + условие некорректное.

Цитата Сообщение от HomBro Посмотреть сообщение
Я не совсем ещё разобрался, как тот код работает
Метод Generate возвращает следующую перестановку вершин. Т.е. если его вызывать, пока он возвращает true, в итоге получатся все перестановки всех вершин. А потом циклом проверяется каждая перестановка - можно ли построить путь по таблице смежности - это если на пути не встречается 0. Больше ничего в том коде нет.

А вообще нужно использовать алгоритм обхода графа в ширину или в глубину.
1
1 / 1 / 1
Регистрация: 14.12.2015
Сообщений: 125
13.12.2016, 09:55  [ТС] 5
Спасибо, попробую
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
13.12.2016, 09:55

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь или здесь.

Работа с графом. Помощь в алгоритме
Помогите с подбором алгоритма для работы с данным заданием. Я рассматривал алгоритм...

API/MFC работа с графом
помогите пожалуйста найти ошибку или дописать недостающее. только недавно полез в апи и мфс,поэтому...

Работа с графом.Найти кратчайший маршрут между двумя вершинами.
Между некоторыми деревнями края Васюки ходят автобусы. Поскольку пассажиропотоки здесь не очень...

Работа с графом (Требуется по заявке клиента предложить способы обмена жилплощади)
В файле записаны предложения по обмену жилплощадью. Имеются варианты размена одной квартиры на две...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.