Основы программирования: Автоматическая обработка ориентированного весового графа(корректура от 20.04.19)

ЗАДАЧА

Найти количество возможных путей в ориентированном весовом графе от вершины до по последнего узла, а также величину кратчайшего пути.

РЕШЕНИЕ

Пусть дан какой либо ориентированный весовой граф например показанный на рисунке 1. Следует написать программу автоматически обрабатывающий этот граф представленный в виде матрицы(массива). Программу будем реализовывать (в учебных целях) на языке Pascal.


рисунок 1

Для создания программы нам нужно придумать алгоритм решения программы. Общий вид алгоритма представлен на рисунке 2. Далее необходимо детализировать каждый блок представленного алгоритма.

Алгоритм представлен в виде ДРАКОН - схемы (ДРАКОН - Дружелюбный Русский Алгоритмический язык Который Обеспечивает Наглядность), которая читается сверху вниз, слева направо. Согласно правил этого языка вертикальная линия соединяющая заголовок алгоритма и его конец называется Царской Дорогой(шампуром на который нанизаны обязательные действия в порядке их исполнения) обеспечивающей наиболее кратчайший путь достижения цели. Все другие вертикальные линии шампуры выполняются после царской дороги и чем правее тем позже.

рисунок 2

Рассмотрим, согласно правилу "черного ящика" или правила матрёшки представленный алгоритм по блокам.

Первый блок - "Представим предложенный граф в виде матрицы состояний" ~~и второй блок - более подробно~~ показан на рисунке 3. ~~Но это показано в общем.~~ Как это сделать показано на рисунке 4 ~~показан алгоритм создания матрицы состояний графа по шагам~~.
Второй блок расшифрован на рисунке 5, который показывает детальный алгоритм поиска возможных путей от вершины графа к последнему узлу. На рисунке 6 приведен граф состояний для приведенного графа с подсчетом возможных маршрутов.

Третий блок - "Ввод данных по весам маршрутов и обработка матрицы по поиску кратчайшего маршрута" показан на рисунке 7, а дерево решений представлено на рисунке 8 для данного графа.

Таким образом Ваша задача сводится к переводу приведенных алгоритмов на язык программирования, с последующим составлением программы