Задача поиска кратчайшего пути¶
Когда вы бродите по интернету, отправляете е-мейл или подключаетесь к лабораторному компьютеру из другого места в кампусе, за кулисами проделывается большая работа по переносу информации с вашего компьютера на другую машину. Углубленное изучение движения информационных потоков через интернет - главная тема предмета “Компьютерные сети”. Однако, в этом разделе мы также обсудим работу интернета в объёме, достаточном для понимания другого очень важного алгоритма на графах.
Рисунок 1: Обзор взаимосвязей в интернете
На рисунке 1 показан высокоуровневый обзор того, как работают коммуникации через интернет. Когда вы используете браузер для запроса веб-страницы с сервера, последний должен уйти из вашей локальной сети дальше в интернет через маршрутизатор. Запрос путешествует по интернету и в конце-концов приходит на маршрутизатор локальной сети, в которой находится сервер. Затем требуемая веб-страница возвращается обратно к вашему браузеру тем же самым путём. Внутри облака, помеченного на рисунке 1 как “Интернет”, располагаются дополнительные маршрутизаторы. Их работа заключается в том, чтобы совместно передавать информацию с места на место. Вы сами можете увидеть множество маршрутизаторов, если ваш компьютер поддерживает команду traceroute. Текст ниже показывает её вывод, чем иллюстрирует наличие тринадцати маршрутизаторов между сервером Luther College и почтовым сервером университета Миннесоты.
- 1 192.203.196.1
2 hilda.luther.edu (216.159.75.1) 3 ICN-Luther-Ether.icn.state.ia.us (207.165.237.137) 4 ICN-ISP-1.icn.state.ia.us (209.56.255.1) 5 p3-0.hsa1.chi1.bbnplanet.net (4.24.202.13) 6 ae-1-54.bbr2.Chicago1.Level3.net (4.68.101.97) 7 so-3-0-0.mpls2.Minneapolis1.Level3.net (64.159.4.214) 8 ge-3-0.hsa2.Minneapolis1.Level3.net (4.68.112.18) 9 p1-0.minnesota.bbnplanet.net (4.24.226.74) 10 TelecomB-BR-01-V4002.ggnet.umn.edu (192.42.152.37) 11 TelecomB-BN-01-Vlan-3000.ggnet.umn.edu (128.101.58.1) 12 TelecomB-CN-01-Vlan-710.ggnet.umn.edu (128.101.80.158) 13 baldrick.cs.umn.edu (128.101.80.129)(N!) 88.631 ms (N!)
Маршрутизаторы на пути через интернет от одного хоста до другого.
Каждый маршрутизатор в интернете соединён с одним или более своими коллегами. Поэтому если вы будете запускать команду traceroute несколько раз в день, то весьма вероятно увидите, что каждый раз информация проходит по новому маршруту. Это происходит из-за определённого количества издержек, ассоциируемого с каждой связью между парами маршрутизаторов в зависимости от объёма трафика, времени суток и многих других факторов. В этот раз мы не удивим вас, сказав, что будем представлять сеть маршрутизаторов в виде графа, чьи рёбра имеют определённый вес.
Рисунок 2: Связи между маршрутизаторами в интернете и их веса.
На рисунке 2 показан небольшой пример взвешенного графа, представляющего взаимосвязи между маршрутизаторами в интернете. Задача, которую мы хотим решить, - это найти путь с наименьшим общим весом, по которому маршрутизатор может передать любое сообщение. Это задание звучит знакомо - нечто подобное мы делали с помощью поиска в ширину. Отличие в том, что здесь мы будем иметь дело с общим весом пути, а не количеством переходов по нему. Следует отметить, что при равенстве всех весов задачи становятся одинаковыми.