Методические указания по выполнению курсовых работ по курсу (стр. 5 из 6)
Режим обучения:
Пользователь выделяет текущую вершину и расставляет метки в смежных с ней вершинах. Если текущая вершина выбрана не правильно или в смежных вершинах нельзя расставить метки, пользователь информируется об этом. После достижения стока, пользователь выбирает ребра, по которым должно происходить насыщение, если ребро выбрано не правильно, то пользователь предупреждается об этом.
5. Задача построения кратчайшего пути от помеченной вершины
Постановка задачи
Задача о нахождении кратчайшего пути между двумя произвольными вершинами формулируется следующим образом: дан взвешенный граф G(V, E, С), необходимо найти путь из вершины s в вершину t такой, чтобы суммарный вес входящих в него ребер был минимальным. Очевидно, что данная задача имеет смысл только в графах, не имеющих контуров с отрицательным весом, иначе проходя по этому контуру сколь угодно большое число раз, можно сколь угодно уменьшать длину пути.
Методы решения
- Алгоритм Форда-Беллмана
Данный алгоритм применим к графам, которые могут иметь отрицательные веса ребер, но не имеют контуров с отрицательным весом. Алгоритм состоит в последовательном построении кратчайших путей из 1, 2 .. k ребер , где k - номер шага алгоритма. На каждом шаге вершинам присваиваются пометки вида [l, k], где l – длина кратчайшего пути, состоящего из не более, чем k ребер, от вершины s. Если в графе нет отрицательных контуров, то кратчайший путь из s в вершину t не может содержать более чем n-1 ребро. Более подробно с данным алгоритмом можно ознакомиться в работах [1, 2].
Шаг 1.
, расставляем пометки: 
.Шаг 2. Обновляем пометки для вершин смежных с вершинами, входящими в
: 
, 
.Шаг 3. Если
и 
, следовательно в графе есть контур отрицательного веса. Выход.Если
и 
, то кратчайшие пути найдены. Выход. 
и 
перейти к шагу 4.Шаг 4. Обновляем множество
: 
, 
. Перейти к шагу 2.Замечание: данный алгоритм используется также при решении задачи поиска всех кратчайших путей от помеченной вершины, с числом ребер не больше
. Для этого алгоритм останавливается на 
итерации, полученные на этом шаге пометки 
являются длинами искомых кратчайших путей.Указания по отображению процесса поиска решения:
Режим демонстрации:
Вершина-источник s и вершина-сток t задаются интерактивно. Отображать пометки вершин, выделять цветом ребра, входящие в кратчайшие пути. На каждом шаге: выделять цветом изменяемые пометки, добавляемые ребра.
Режим обучения:
На первом этапе пользователь задает начальную вершину
. Пользователь выбирает вершины, пометки в которых должны быть изменены. Если выбор правильный, то пометка изменяется, вершина и соответствующий кратчайший путь выделяются цветом. Если выбор не правильный, то пользователь предупреждается об этом.- Алгоритм Дейкстры
Алгоритм Дейкстры рассчитан на случай, когда веса всех ребер неотрицательные:
. В процессе поиска решения вершинам присваиваются пометки, которые могут быть двух видов: (#) временные, (*) – постоянные.Также с данным алгоритмом можно ознакомиться в работах [2, 3].
Шаг 1. Вершине s присваиваем пометку [0, *], всем вершинам
присваиваем пометку [0, #]. Помечаем вершину s как текущую p = s.Шаг 2.
и имеющих временные пометки, изменить пометку на [ 
, #], где 
.Шаг 3. Для
такой, что 
из всех 
, имеющих временную пометку, изменить пометку на постоянную 
, p = .Шаг 4. Если p=t, остановиться. Иначе переход на Шаг 2.
Замечание: если необходимо найти все кратчайшие пути от вершины s, то условием останова является наличие у всех вершин графа постоянных пометок.
Указания по отображению процесса поиска решения:
Режим демонстрации:
Вершина-источник s и вершина-сток t задаются интерактивно. Для каждой вершины графа отображать пометку [
, #(*)]. На каждом шаге: изменять значения пометок, выделять цветом пометку, измененную на постоянную на последнем шаге, выделять изменяемые на текущем шаге временные пометки. Кратчайшие пути и вершины с постоянными пометками выделять цветом.Режим обучения:
В данном режиме пользователь выбирает вершины, временная пометка которых должна быть изменена, изменяет наименьшую временную пометку на постоянную. Если выбор правильный, то пометка изменяется, вершина и соответствующий кратчайший путь выделяются цветом. Если выбор не правильный, то пользователь предупреждается об этом.
6. Задача о максиминном пути
Постановка задачи
Задача о максимином пути относится к так называемым задачам поиска узких мест. В данном случае дан взвешенный граф G(V, E, С), веса ребер
интерпретируются как пропускная способность. Необходимо найти путь из вершины s в вершину t, обладающий наибольшей пропускной способностью, то есть вес наименьшего ребра, входящего в путь, должен быть максимальным. [1]Пусть имеется некоторый путь
в графе G из вершины s в вершину t, состоящий k из ребер, тогда пропускная способность пути будет вычисляться как 
. Решением исходной задачи будет 
.Методы решения
- Алгоритм Дейкстры
Метод решения данной задачи основан на модификации исходного алгоритма Дейкстры, где сумма заменяется минимумом, а минимум меняется на максимум.
Шаг 1. Вершине s присваиваем пометку [0, *], всем вершинам
присваиваем пометку [∞, #]. Помечаем вершину s как текущую p = s.Шаг 2.
и имеющих временные пометки, изменить пометку на [ , #], где 
.Шаг 3. Для
такой, что 
из всех , имеющих временную пометку, изменить пометку на постоянную 
, p = .Шаг 4. Если p=t, остановиться. Иначе переход на Шаг 2.
Указания по отображению процесса поиска решения:
Режим демонстрации:
Для каждой вершины графа отображать пометку [
, #(*)]. На каждом шаге: изменять значения пометок, выделять цветом пометку, измененную на постоянную на последнем шаге, выделять изменяемые на текущем шаге временные пометки. Максиминные пути и вершины с постоянными пометками выделять цветом.