Практикум по дисциплине «Дискретная математика»
жүктеу/скачать 0,98 Mb.
|
[ZHitnikova N.I.] Teoriya grafov. Praktikum(z-lib.org)
| Пример
Найдем минимальный путь из вершины v2 в v6 в ориентированном нагруженном графе D, изображенном на рис. 9. В рассматриваемом графе количество вершин n=7, следовательно, матрица длин дуг ориентированного графа D будет иметь размерность 7×7. 
Рис. 9.
 .
Согласно алгоритму, составляем таблицу стоимости минимальных путей из вершины v2 в вершину vi не более, чем за k шагов, k=0,…n-1 (n=7, следовательно, k=0,…6). Как было определено выше,  , и  для всех остальных вершин vi ≠ v2, то есть первый столбец таблицы состоит из элементов, равных  , кроме элемента  . Второй столбец таблицы повторяет вторую строку матрицы стоимости, поскольку представляет собой стоимость возможных путей из вершины v2 за один шаг. Далее по формуле (3.1) находим по столбцам все оставшиеся элементы таблицы. Например, чтобы найти элемент  , складываем элементы столбца  и первого столбца матрицы стоимости и выбираем минимальное из получившихся чисел:
 .
В конечном итоге получаем следующую таблицу: 
Теперь необходимо по построенной таблице и по матрице C(D) восстановить минимальный путь из вершины v2 в v6, который будет строиться с конца, то есть, начиная с вершины v6. Для этого выбираем минимальное из чисел, стоящих в строке, соответствующей v6 в таблице. Это число – 21 – длина минимального искомого пути. В первый раз такая длина была получена при количестве шагов, равном 4. В вершину v6 мы можем попасть за один шаг из вершин v1 и v7 (длина соответствующих дуг 8 и 5 соответственно – данные из матрицы C(D)). Выбираем минимальную по длине из этих дуг. Далее, в вершину v7 можно попасть из v4 и v5 (длина соответствующих дуг 7 и 3 соответственно). Продолжая аналогичным образом, найдем искомый путь за 4 шага минимальной длины из вершины v2 в v6: v2 v3 v5 v7 v6. жүктеу/скачать 0,98 Mb. Достарыңызбен бөлісу:
|