Определение наикратчайшего пути между вершинами ориентированного графа с циклами

Пример 4. Определить наикратчайший путь между вершиной 1 и вершиной 7 на графе с циклами представленном на рис.21.

Рис.21

Для решения транспортной задачи в процедуре EXCEL «Поиск решения», представим ее как транспортную задачу с промежуточными пунктами. Будем считать, что транспортные расходы при перевозке одной единицы груза равны (в условных единицах) расстояниям между вершинами. Одна единица груза отправляется из вершины 1 (исходный пункт) и должна прибыть в вершину 7 (пункт назначения). Вершины 2, 3, 4, 5, 6 рассматриваются как промежуточные пункты, которые являются одновременно и исходными пунктами и пунктами назначения.

Требуется определить такую последовательность вершин, по которым должна перемещаться единица груза отправленная из вершины 1, при которой стоимость транспортных расходов будет минимальна и груз попадет в вершину 7.

Так как транспортные расходы при перемещении груза из одной вершины в другую равны расстоянию между вершинами, то последовательность вершин при которой транспортные расходы будут минимальными определяет наикратчайший путь из вершину 1 в вершину 7. Матрица транспортных расходов, соответствующая данному графу представлена на рис.22.

Рис.22

Буквой М обозначается случай когда между соответствующими вершинами нет пути. В качестве М берут число, значительно большее самого большего пути. В данной задаче наибольший путь между 5-й и 7-ой вершинами, поэтому можно взять, например, М=50. Для промежуточных пунктов 2, 3, 4, 5, 6 должны быть предусмотрены буферные емкости В. Буферная емкость должна быть не меньшей, чем количество груза, которое перемещается в сети описываемой графом. В данной задаче - В=1. После введения буферных емкостей в первый столбец и нижнюю строку таблицы и замены М=50, получим транспортную задачу, представляющую задачу о назначениях (Рис.23).

Рис.23