Определение кратчайшего расстояния между ГО и ГП

Метод потенциалов.

Метод основан на приписывании вершинам временных пометок, которые дают верхнюю границу длины от начальной вершины до этой вершины.

Алгоритм

определения кратчайших расстояний методом потенциалов:

. Начальной точке сети, за которую может быть принята любая из вершин, присваивают потенциал, равный нулю (vi

= 0

).

. Определяют потенциалы соседних с начальной точкой вершин сети по формуле

vj = vi + lij,

где:

vi - потенциал предшествующей (соседней) вершины;

lij - длина звена, соединяющего вершины i и j.

Из них выбирают наименьший потенциал и присваивают его соответствующей вершине. Выбранный потенциал определяет кратчайшее расстояние от начальной точки до данной, на сети эту связь отмечают стрелкой.

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

Полное решение задачи включает столько этапов, сколько вершин включает транспортная сеть, поскольку каждый раз определяют кратчайшие расстояния от начальной точки до остальных.

Кратчайшие расстояния от точки А1.

А1 - А1 = 0

А1 - A2 = 4

А1 - А3 = 5 + 7 = 12

А1 - А4 = 5 + 4 = 9

А1 - Б1 = 5 + 3 = 8

А1 - Б2 = 4 + 8 = 12

А1 - Б3 = 4 + 8 + 4 = 16

А1 - Б4 = 4

А1 - Б5 = 5 + 4 = 9

А1 - Б6 = 7

А1 - Б7 = 5

Полученная таблица кратчайших расстояний.

Таблица № 2