ма вузлами мережі. Наприклад, найкоротша відстань між вузлами 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 ...
