Постановка задачи о кратчайшем пути на сети
На сети, что задается графом (I,U), где I — множество вершин, U — множество дуг, с определенной на ней функцией стоимости сіj ((і,j) — дуга с U), для фиксированных i1 и is найти путь = ((i1,i2),(i2,i3) .,(is-1,is)) из вершины i1 в вершину is, длина которого
наименьшая. 1.2 Описание метода Минти Метод Минти решения задачи о кратчайшем пути в сети представляет собой итеративный процесс, в ходе которого строится путь L=(s=i0, i1, ., ip-1, ip=t). На предварительном (нулевом) этапе алгоритма: · формируется массив значений так называемых модифицированных длин · осуществляется отметка вершины i0 = s числом mi0 = 0. Стандартная итерация включает этапы: . Отметка вершин сети. Обозначим множество вершин cети, отмеченных на предыдущих итерациях, как Если среди вновь помеченных вершин окажется вершина t, то, значит, найден искомый путь (i0, i1, ., i(p-1), ip), гдена чем алгоритм завершается. В случае, если вершины t нет среди отмеченных, и одновременно нельзя отметить ни одной новой вершины, то переходим к этапу 2. . Преобразование значений модифицированных длин дуг. Для каждой вершины i∊ Затем происходит переход к следующей итерации. Путь, построенный по методу Минти, будет кратчайшим. Это можно доказать с помощью индукции по номеру итерации, на которой была помечена вершина t, или, что то же самое, по количеству дуг, составляющих кратчайший путь. Если это произошло на первом шаге (что возможно только в случае, если начальная и конечная вершины соединены дугой нулевой длины), то доказываемое утверждение очевидно. Предположим, что оно верно для всех пунктов, помеченных за первые r итераций, т. е. тех, которые достигаются переходом по r дугам. Тогда, если конечная вершина t помечена на (r + 1)-ой итерации, то полученный путь также будет кратчайшим, так как данная вершина помечается в результате минимально возможного продолжения одного из путей, полученного за предыдущие r итераций и являющегося по предположению кратчайшим.
Перейти на страницу: 1 2
|