овідає пара паралельних ребер, по кожному з яких дані передаються в одному напрямку. У такій мережі для передачі пакета від вузла-джерела вузлу-одержувача по різних лініях через кілька комутаторів пакетів потрібно прийняти рішення про вибір маршруту. Це завдання еквівалентна пошуку шляху в графі. Якщо два маршрутизатора безпосередньо сполучені до однієї і тієї ж локальної або глобальної мережі, тоді це двосторонньо з'єднання відповідає парі паралельних ребер, що з'єднують відповідні вершини. Якщо до мережі безпосередньо приєднані більше двох маршрутизаторів, тоді ця мережа представляється у вигляді безлічі пар паралельних ребер, кожна з яких з'єднує два маршрутизатора. В об'єднаній мережі для передачі IP-дейтаграми від маршрутизатора-джерела до маршрутизатора-приймачу по різних лініях через різні мережі і маршрутизатори пакетів потрібно прийняти рішення про вибір маршруту. Якщо вибирається маршрут з мінімальною кількістю ретрансляційних ділянок (хопов), тоді кожному ребру, відповідному ретрансляційних ділянці, призначається одиничний вагу. Це завдання відповідає пошуку найкоротшого шляху в звичайному (не виважених) графі. Але найчастіше кожному ретрансляційних ділянці у відповідність ставиться певна величина, звана вартістю (cost) передачі. Ця величина може бути обернено пропорційною пропускної здатності лінії, прямо пропорційною поточної навантаженні на цю лінію або являти собою якусь комбінацію подібних параметрів. Вартість використання ретрансляційного ділянки може бути різною в різних напрямках. Наприклад, це справедливо у випадку, якщо вартість використання ретрансляційного ділянки пропорційна довжині черги дейтаграм, що чекають передачі. У теорії графів завданню знаходження шляху з найменшою вартістю відповідає завдання пошуку шляху з найменшою довжиною в підвішеному орієнтованому графі. br/>
2. Вихідні дані
Варіант № 122
В
Рисунок 2 - Матриця суміжності
В
Малюнок 2.1 - Зважений орієнтовний граф
3. Алгоритм Дейкстри
Алгоритм знаходить найкоротші шляхи від даної вершини-джерела до всіх інших вершин, перебираючи шляху в порядку збільшення їх довжин. Робота алгоритму проходить поетапно. До k-му кроці алгоритм знаходить k найкоротших (з найменшою вартістю) шляхів до k вершин, найближчим до вершині-джерела. Ці вершини утворюють безліч Т. На кроці (k + 1) до безлічі Т додається вершина, найближча до вершини-джерела серед вершин, що не входять в безліч Т. При додаванні кожної нової вершини до безлічі Т визначається шлях до неї від джерела. Дерево - сполучна дерево для вершин, що належать безлічі Т, включаючи ребра, що входять в дорозі з найменшою вартістю від вершини s до кожної вершини безлічі Т. Введемо позначення: N - безліч вершин мережі; s - вершина-джерело; Т - безліч вершин, ...
