Этап 1. Нахождение кратчайшей сети, связывающей все пункты

Назовем все пункты, указанные на рис.1, вершинами сети, а линию, соединяющую две соседние вершины, - звеном.

Кратчайшей связывающей сетью называется незамкнутая сеть, связывающая две и более вершины с минимальной суммарной длиной всех соединяющих их звеньев.

На схеме (рис.1)находится наименьшее звено. В данном случае это звено В-Г = 2 км. Затем рассматриваются все звенья, связанные одной из своих вершин с выбранным звеном, т.е. звенья: В-А = 9 км, В-Б = 3 км, В-Д = 4 км, Г-Б = 2 км, Г-Д = 4 км, Г - Е = 4 км. Из них выбирается звено с наименьшим расстоянием (Г - Б = 2 км). Далее рассматриваются все звенья, связанные с вершинами полученной ломаной линии В-Г-Б, из них выбирается наименьшее, и так до тех пор, пока не будут выбраны все вершины сети. При этом нельзя выбирать звено, соединяющее две ранее включенные в сеть вершины. На рис. 2 представлена кратчайшая связывающая сеть для рассматриваемого примера. Около каждого пункта проставлено количество ввозимого (цифра в квадратике) и вывозимого грузов (цифра в треугольнике).

Таблица 1 Исходные данные для расчета