    Сейчас на сайте: 1 посетителей (1 зарегистрированных, 0 гостей) |   426057681  574055213 |  Партнерам |  Авторам |  Покупателям |
Кратчайшие пути
| контрольные работы, Разное Объем работы: 5 стр. Год сдачи: 2010 Стоимость: 300 руб. Просмотров: 513 | Не подходит работа? |
Оглавление
Введение
Заключение
Заказать работу
Граф задан матрицей весов. С помощью алгоритма Дейкстры найдите кратчайшие пути от вер-
шины v10 до всех остальных. (Вершины нумеруются с нуля!)
шины v10 до всех остальных. (Вершины нумеруются с нуля!)
Обозначения
• V — множество вершин графа
• E — множество ребер графа
• w[ij] — вес (длина) ребра ij
• a — вершина, расстояния от которой ищутся
• U — множество посещенных вершин
• d[u] — по окончании работы алгоритма равно длине кратчайшего пути из a до вершины u
• p[u] — по окончании работы алгоритма содержит кратчайший путь из a в u
• V — множество вершин графа
• E — множество ребер графа
• w[ij] — вес (длина) ребра ij
• a — вершина, расстояния от которой ищутся
• U — множество посещенных вершин
• d[u] — по окончании работы алгоритма равно длине кратчайшего пути из a до вершины u
• p[u] — по окончании работы алгоритма содержит кратчайший путь из a в u
Описание
В простейшей реализации для хранения чисел d[i] можно использовать массив чисел, а для хранения принадлежности элемента множеству U — массив булевых переменных.
В начале алгоритма расстояние для начальной вершины полагается равным нулю, а все остальные расстояния заполняются большим положительным числом (бо́льшим максимального возможного пути в графе). Массив флагов заполняется нулями. Затем запускается основной цикл.
В простейшей реализации для хранения чисел d[i] можно использовать массив чисел, а для хранения принадлежности элемента множеству U — массив булевых переменных.
В начале алгоритма расстояние для начальной вершины полагается равным нулю, а все остальные расстояния заполняются большим положительным числом (бо́льшим максимального возможного пути в графе). Массив флагов заполняется нулями. Затем запускается основной цикл.
После офорления заказа Вам будут доступны содержание, введение, список литературы*
*- если автор дал согласие и выложил это описание.