Глава 21. Кратчайшие пути. о 21.7.Разработайте генератор насыщенных (плотных) случайных сетей, основанный на программе 17.13, и генератор весов ребер по методике

о 21.7. Разработайте генератор насыщенных (плотных) случайных сетей, основанный на программе 17.13, и генератор весов ребер по методике, описанной в упражнении 21.6. Напишите клиентские программы, порождающие случайные сети для обоих распре­делений веса с так подобранным набором значений К и Е, чтобы можно было исполь­зовать их для выполнения эмпирических тестов на графах, получаемых из упомянутых моделей.

21.8. Реализуйте независимую от представления сети клиентскую функцию, которая строит сеть, получая из стандартного ввода ребра с весами (пары целых чисел из ди­апазона от 0 до V- 1 с весами между 0 и 1).

• 21.9. Напишите программу, которая генерирует V случайных точек на плоскости, за­тем строит сеть с ребрами (в обоих направлениях), соединяющими все пары точек, расположенных на расстоянии, которое не превышает заданное d (см. упражнение 17.74), и устанавливает вес каждого ребра равным расстоянию между двумя точками, соединенными этим ребром. Определите, как установить d, чтобы ожидаемое число ребер было равно Е.

о 21.10. Разработайте базовый класс и производные классы, реализующие АТД для гра­фов, которые могут быть неориентироваными или ориентированными, взвешенными или невзвешенными и насыщенными или разреженными.

> 21.11. Назначение следующей таблицы из опубликованной дорожной карты — дать длину кратчайших маршрутов, соединяющих города. Она содержит ошибку. Откоррек­тируйте таблицу. Добавьте также таблицу в стиле рис. 21.4, которая показывает, как проследовать по кратчайшему маршруту.