В общем случае строятся p деревьев кратчайших путей. Нам нужно построить 5 деревьев.
Построим эти деревья, зная длины кратчайших путей (они стоят в матрице D5) и ориентируясь по диаграмме на рис. 9.
Деревья показаны на рис. 10.
Замечание. Если в графе отсутствуют контуры отрицательной длины, то в каждой строке и каждом столбце матрицы Dp по крайней мере одна длина сохраняется такой же, какой она была в матрице D0 (длина кратчайшего пути из одной дуги). В нашем случае имеем:
Эти числа показаны в матрице жирным шрифтом и подчеркнуты. Только из соответствующих дуг и могут состоять деревья кратчайших путей, каждый подпуть в которых, в частности, путь из одной дуги, - кратчайший.
Если указанное условие не выполняется, в графе имеются контуры отрицательной длины, и задача о кратчайшем пути не имеет решений.
Сайт КГТА http://www.dksta.ru (отсутствует третья часть адреса).
Сайт (адрес сервера) фирмы Mathsoft – производителя системы MathCAD
http://www.mathsoft.com/appsindex.html.
Программой – клиентом, которая находится на компьютере пользователя и с помощью которой можно пользоваться услугами сервера, является программа Internet Explorer (буквально, «проводник» Интернет).
Принципы функционирования INTERNET
Функционирование Internet основано на:
1) принципе взаимодействия протоколов разных уровней;
2) следующий принцип Internet – это принятая модель взаимодействия в сети типа «клиент–сервер»;
3) еще один принцип – единая система адресации информационных ресурсов.
При рассмотрении ранее организации обмена информацией в любых сетях была рассмотрена общая модель взаимодействия открытых систем, включающая в себя семь уровней взаимодействия.
При рассмотрении функционирования Internet можно укрупнённо выделить четыре уровня протоколов, отображенных в табл. 13.1.
Таблица 13.1
Уровни
Протоколы (службы)
I
SMTP,
РOP3
(E–mail)
Usenet
Telnet
FTP
WWW
II
TCP (Transmission Control Protocol)
III
IP (Internet Protocol)
IV
Ethernet, Arcnet, Token Ring и др.
Самый нижний ( уровень IV) соответствует уровням доступа к сети физическому и соединения. На этом уровне используются протоколы взаимодействия в различных структурах соединения локальных сетей (Ethernet – шинная структура, Arcnet – звёздная, Token Ring – кольцевая).
Протоколы данного уровня обеспечивают передачу пакетов данных в сети на уровне аппаратных средств.
Уровень III. Это уровень межсетевого взаимодействия для передачи пакетов данных из одной подсети в другую. На этом уровне используется адресный протокол IP.
Уровень II. Это транспортный уровень. Протокол ТСР обеспечивает передачу пакетов данных между прикладными программами за счёт образования виртуальных соединений между ними.
Уровень I. Это верхний уровень, называемый прикладным. На этом уровне осуществляется доступ с одной стороны к информационным ресурсам Internet (наборам данных и программам, хранящихся на компьютерах сети), а с другой стороны – к программам – клиентам, находящимся на компьютере пользователя и выдающим ему найденную в сети и доставленную информацию.