Алгоритм решения задачи 2

Будем постепенно приписывать к вершинам графа целые числа – индексы:

1.Вершине А припишем индекс 0.

2. Всем вершинам, смежным с А припишем индекс 1.

3. Всем вершинам смежным с вершинами индекса 1 и не помеченным индексами, припишем индекс 2 и т.д.

4. Как только вершина В получит некоторый индекс, процесс останавливаем (даже если остались не помеченные вершины).

Число n - это и есть длина кратчайшего пути.

Построим этот путь.

5. Среди вершин смежных с В, обязательно найдется вершина С с индексом n-1

(одна или несколько), возвращаемся в вершину С и продолжаем процесс.

6. Через n шагов придем в вершину с индексом 0, т.е. в А.

Один или несколько путей построены.

Задача 3. Если к каждой дуге (ребру) графа поставить в соответствие некоторое

число λ_k ≥ 0 (вес дуги), то граф называется взвешенным (или нагруженным).

3 • • 5

А • • В

7 6

•

Итак, требуется найти кратчайший путь из А в В в смысле суммы весов

(т.е. ∑ λ _к – минимальна)

Разработан эффективный алгоритм

Дата добавления: 2014-01-06