IV. Решение некоторых типовых заданий

III. Самостоятельная работа 8.

1. Найти кратчайший путь из вершины в вершину в заданном графе.

2. Найти кратчайший путь из вершины в вершину во взвешенном графе.

1. Найти кратчайший путь из вершины в вершину в заданном графе.

Решение. Используем алгоритм задачи о нахождении кратчайшего пути из А в В в смысле наименьшего количества ребер.

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

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

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

4. Всем вершинам, смежным с вершинами индекса 2 и не имеющим индекса, припишем индекс 3. В нашем случае, в этот момент вершина В также получит индекс 3.

Процесс останавливаем (несмотря на то, что остались непомеченные вершины).

Таким образом, мы нашли длину кратчайшего пути.

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

5. Вершина В имеет индекс 3. Среди смежных с ней вершин есть вершина индекса, на единицу меньшего, чем 3, то есть, индекса 2. Перейдём из В к этой вершине (в нашем случае такая вершина одна).

6. Среди вершин, смежных с найденной вершиной индекса 2 есть вершина индекса, на единицу меньшего, то есть, индекса 1 (такая вершина также в нашем случае единственна). Перейдём к ней.

7. Вершина индекса 1 смежна с вершиной А. Переходя от неё к А, заканчиваем построение кратчайшего пути в заданном невзвешенном графе.

V. Расчётно-графическая работа. Задание 1.

Дата добавления: 2014-11-25