Алгоритм построения и использования таблицы оптимальных путей транспортной сети

Алгоритм построения ТОП состоит из следующих действий:

1. заполнить первый и второй столбцы ТОП номерами вершин транспортной сети в порядке их возрастания. Во втором столбце одну или несколько начальных вершин пометить, например, знаком минус перед номерами вершины. Третий столбец заполнить исходными потенциалами вершин. Исходные потенциалы начальных вершин равны нулю, а всех остальных вершин – числу М или максимально большому числу;
2. для всех дуг, исходящих из помеченной вершины, проверяется условие оптимальности дуги pppj−> i ij , т.е. разность потенциалов конечной и начальной вершин дуги должна быть больше оценки дуги между этими вершинами. Выполнение этого условия говорит о выгодности движения по данной дуге. Тогда в качестве предшествующей вершины для конечной вершины дуги (второй столбец ТОП) указывается номер вершины i (с пометкой). Потенциал конечной вершины определяется как сумма потенциала начальной вершины дуги и оценки этой дуги, т.е. pj= pp i + ij ;
3. если условие оптимальности дуги не выполняется, то проверяется следующая дуга, исходящая из помеченной вершины;
4. если условие оптимальности проверено для всех дуг, исходящих из помеченной вершины, то метка с этой вершины снимается, и рассматриваются дуги, исходящие из любой следующей помеченной вершины, то все действия, начиная со второго, повторяются. Построения оптимальных маршрутов повторяется до тех пор, пока в ТОП имеется хотя бы одна помеченная вершина.