18. Задача о кротчайшем пути в транспортной сетиПусть задана транспортная сеть, в которой отмечены вершина с индексом 0 (вход) и вершина N (выход), и заданы длины дуг Lij, связывающих вершины. Требуется найти путь кратчайшей длины от входа к выходу. Обозначим через Fiдлину кратчайшего пути от i -ой вершины до N-й. Тогда FN=0 и для остальных вершин по принципу оптимальности (из какой бы вершины i мы не исходили и в какую бы вершину j мы не перешли, дальнейший путь должен быть кратчайшим). Для решения полученной системы можно воспользоваться приближением в пространстве функций, приняв за начальную функцию, равную нулю при i=N и бесконечности (большому числу) при остальных i. Осуществляем итерационный процесс до совпадения k-го и (k-1)-го приближений. Если к тому же запоминать для каждого i индекс последующей вершины j, обеспечивающий минимум, то можно будет найти искомый кратчайший путь. Ускорения сходимости процесса итераций можно добиться, если при поиске k-го приближения ссылаться не на (k-1)-е приближение, а на последнюю из полученных оценок:
|
