Основные понятия сетевых моделей. Матричный способ задания сетей. Задача о кратчайшем пути, как одна из наиболее важных оптимизационных задач на сети. Выполнение алгоритма (шаги) Дейкстры непосредственно на сети. Построение схем сетевой модели задачи.
Аннотация к работе
СЕТЕВЫЕ МОДЕЛИ ЗАДАЧ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ.Граф - это совокупность множества узловых точек X (узлов или вершин) и множества соединяющих их дуг А. Обычно вершинам приписывают номера - 1, 2,..., n, а дуги изображают прямыми или кривыми линиями, каждая из которых соединяет ровно две вершины, и обозначают (i, j). Вершины в графе называются смежными, если они различны и существует дуга, соединяющая эти вершины. Если все дуги пути, связывающего узлы i и j, ориентированы так, что действительно можно пройти по этому пути из i и j, то такой путь часто называют ориентированной цепью. Важным частным случаем сети является связная сеть, содержащая n узлов и n-1 дугу.