Теми рефератів
> Реферати > Курсові роботи > Звіти з практики > Курсові проекти > Питання та відповіді > Ессе > Доклади > Учбові матеріали > Контрольні роботи > Методички > Лекції > Твори > Підручники > Статті Контакти
Реферати, твори, дипломи, практика » Курсовые проекты » Алгоритми маршрутизації

Реферат Алгоритми маршрутизації





ма вузлами мережі. Наприклад, найкоротша відстань між вузлами 1 і 5 одно d 15=12.

Для знаходження відповідних маршрутів нагадаємо, що сегмент маршруту (i, j) складається з ребра (i, j) тільки в тому випадку, коли s ij=j. В іншому випадку вузли i і jсвязани, принаймні, через один проміжний вузол. Наприклад, оскільки s 15=4 і s 45=5, спочатку найкоротший маршрут між вузлами 1 і 5 буде мати вигляд 1 gt; 4- gt; 5. Але так як s 14 не дорівнює 4, вузли 1 і 4 в певному шляху не пов'язані одним ребром (але в вихідної мережі вони можуть бути пов'язані безпосередньо). Далі слід визначити проміжний вузол (вузли) між першим і четвертим вузлами. Маємо s 14=2 і s 24=4, тому маршрут 1 gt; 4 замінюємо 1- gt; 2- gt; 4. Оскільки s 12=2 і s 24=4, інших проміжних вузлів немає. Комбінуючи певні сегменти маршруту, остаточно отримуємо наступний найкоротший шлях від вузла 1 до вузла 5: 1 gt; 2- gt; 4- gt; 5. Довжина цього шляху дорівнює 12 кілометрам.


Глава 3. Розробка алгоритмів маршрутизації


. 1 Розробка алгоритму маршрутизації Дейкстри


Рис.25. Блок схема алгоритми? тма Де? йкстри

алгоритми? тм Де? йкстри реалізований на мові програмування C #


using System; .Collections.Generic; .Linq; .Text; ConsoleApplication18

{Program

{public class Node

{List lt; Link gt; Links {get; set; } Node ()

{= new List lt; Link gt; ();

}

} public class Link

{double Distance {get; set; } string Node {get; set; }

} public class Description

{Visited {get; set; } double Distance {get; set; } Description ()

{= false;=double.PositiveInfinity;//+ 8

}

} public class Graph

{Dictionary lt; string, Node gt; nodes; Graph ()

{= new Dictionary lt; string, Node gt; ();

} void AddNode (string name)

{. Add (name, new Node ());

} void AddLinkToNode (string start, string end, double distance, boolisOriented)

{[start] .Links.Add (new Link {Node=end, Distance=distance}); (! isOriented) [end] .Links.Add (new Link {Node=start, Distance =distance});

} double FindShortestDistance (string start, string end)

{

//АлгорітмДейкстри lt; string, Description gt; info=new Dictionary lt; string, Description gt; (this.nodes.Count); (string current in this.nodes.Keys) .Add (current, new Description ());//visited, distance

info [start] .Distance=0;

//Поки всі вершини невідвідані

while (! info.Select (x= gt; x.Value.Visited) .Aggregate ((x, y)= gt; x amp; y))

{

//Знаходимо невідвідування вершину з мінімальною міткою

string current=info.Where (x= gt;! x.Value.Visited

amp; amp; x.Value.Distance == info.Where (y= gt;! y.Value.Visited) .Min (y= gt; y.Value.Distance))

. First (). Key;

//Знаходимо всі невідвідані сусідні вершини для поточної вершини

List lt; Link gt; neighbors=nodes [current] .Links.Where (x= gt;! info [x.Node] .Visited) .ToList ();

//Розглядаємо нову довжину шляху для кожної сусідньої вершини

foreach (Link link in neighbors)

{distance=info [current] .Distance + link.Distance; (info [link.Node] .Distance gt; distance) [link.Node] .Distance=distance;

}

//Відзначаємо поточну вершину як відвідана.

info [current] .Visited=true;

} info [end] .Distance;

}

} void Main ()

{count=10; [] names={ 1 raquo ;, 2 raquo ;, 3 raquo ;, 4 raquo ;, 5 raquo ;, 6 raquo ;, 7 raquo ;, 8 raquo ;, 9 raquo ;, 10 };=NewGraph ();

//Заполненіеграфавершінамі. (inti=0; i lt; count; ++ i)

graph.AddNode (names [i]);

//Створення у вершин зв'язків.

//Останнє значення говорить про те, що цей зв'язок двунаправленная.

graph.AddLinkToNode ( 1 raquo ;, 2 raquo ;, 7, false);

graph.AddLinkToNode ( 1 raquo ;, 3 raquo ;, 9, false);

graph.AddLinkToNode ( 1 ...


Назад | сторінка 5 з 7 | Наступна сторінка





Схожі реферати:

  • Реферат на тему: The structure, particularities and meaning of distance learning
  • Реферат на тему: Розробка Web-додатки з використанням JavaScript каркаса Node.js
  • Реферат на тему: Облікова політика ТОО &Link Sys&
  • Реферат на тему: Команди налаштування, пошуку та усунення неполадок комутатора D-Link DES-30 ...
  • Реферат на тему: Арабо-ізраїльський конфлікт: особливості висвітлення в мережевих ЗМІ (на пр ...