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