Учебная работа № 6618. «Контрольная Задача на нахождение кратчайшего пути вариант 8
Учебная работа № 6618. «Контрольная Задача на нахождение кратчайшего пути вариант 8
Содержание:
«Задача 3. (кратчайшие пути) Найти кратчайшие пути, ведущие из узла А во все другие узлы.
Вариант 8
A B C D E F G
A — 36 33 — — — 14
B — 25 — 19 13 —
C — 23 — 5 15
D — 17 — 8
E — 25 —
F — 22
G —
Задача состоит в нахождении путей минимальной длины пути от вершины-источника до всех остальных вершин. Для решения этой задачи обычно применяется алгоритм Дейкстры.
Форма заказа готовой работы
Выдержка из похожей работы
Основой методов
сетевого планирования является сетевая
модель (сетевой график), отражающая
логическую взаимосвязь работ, входящий
в некоторый комплекс, что позволяет
осуществлять управление ходом выполнения
этих работ,
Для
построения сетевой модели необходимо,
прежде всего, разбить весь комплекс на
отдельные работы или операции и составить
очередность выполнения этих работ,
Для этого составляется список работ,
которые непосредственно предшествуют
каждой работе, а так же планируется
время, необходимое для их выполнения,
Полученные данные
удобно заносить в таблицу, В таблице 1
приведены данные для проекта, состоящего
из девяти работ,
Таблица 1
№ работы
1
2
3
4
5
6
7
8
9
Предшествующие
работы
—
—
1
1,
2
1,
2
3,
4
3,
4
6
7,
5
Продолжительность
работы
10
15
5
20
15
6
8
10
15
На
основании данных, приведенных в таблице,
строится график комплекса работ,
входящих в проект, Каждая работа
изображается в виде ориентированного
отрезка (дуги), Связи между работами
изображаются пунктирными линиями
(дуги-связи), В результате получается
сетевой график (начальная вершина дуги
– начало, а конечная – завершение
соответствующей работы):
Рис,
3,
Предварительно
следует упростить полученную сеть,
Можно удалить некоторые дуги-связи, а
начало и конец удаляемой дуги объединить
в одну вер-шину, На рис, 2 изображена
сеть, полученная после упрощения сети,
изобра-женной на рис, 1,
Рис,
4,
В
сетевом графике каждая вершина является
конечной для некоторых дуг(операций),
входящих в нее или начальной для дуг
(операций) из нее выходящих, Поэтому
каждая вершина может трактоваться как
событие, означающее завершение всех
операций (дуг), для которых она является
конечной и возможность начала
выполнения всех операций (дуг), для
которых она является начальной,
Начальной вершине соответствует событие,
под которым подразумевается начало
осуществления проекта, а конечной
вершине соответствует событие –
завершения выполнения всего комплекса
работ
