Детальная постановка задачи
Дан неориентированный граф с количеством вершин size и инициализированным весов ребер. Необходимо определить кратчайший путь из заданной вершины в заданную через вершины графа. И вывести на экран суммарный вес ребер, через которые проходит этот путь. Все соседи вершины 1 проверены. Текущее минимальное расстояние до вершины 1 считается окончательным изменению не подлежит. Вершина 1 отмечается как… Читать ещё >
Детальная постановка задачи (реферат, курсовая, диплом, контрольная)
Условие поставленной передо мной задачи выглядит следующим образом:
Дан неориентированный граф с количеством вершин size и инициализированным весов ребер. Необходимо определить кратчайший путь из заданной вершины в заданную через вершины графа. И вывести на экран суммарный вес ребер, через которые проходит этот путь.
Пример выполнения задания:
Необходимо найти кратчайший путь из 1 в 5.
- 1) Метка вершины 1 полагается равной 0, метки остальных вершин — недостижимое большое число.
- 2) Первый шаг:
Обходим соседей вершины 1 по очереди.
Для вершины 2: длина пути в нее через вершину 1 равна сумме метки вершины 1 и длины ребра, соединяющих вершины 1 и 2.
Получаем: 0+7=7.
Так как 7 <? , то меняем метку вершины 2 на 7.
Аналогично находим метки для вершин 3 и 6:
для 3: 0+9=9.
для 6: 0+14=14.
Все соседи вершины 1 проверены. Текущее минимальное расстояние до вершины 1 считается окончательным изменению не подлежит. Вершина 1 отмечается как посещенная.
3) Второй шаг:
Обходим соседей вершины 2. (так как метка у вершины 2 меньше всех остальных) для 3: 7+10 =17 (так как 9<17, то метка не меняется) для 4: 7+15=22.
4) Третий шаг:
Обходим соседей вершины 3:
5) Четвертый шаг:
Обходим соседей вершины 6:
для 5: 11+9=20.
6) Пятый шаг:
Конечный ответ: 20.