Программа находит кратчайший путь по алгоритму Дейкстры, как разобраться в коде - C#
Формулировка задачи:
У меня есть прога, которая находит кратчайший путь по алгоритму дейкстры, с графическим оформлением, нужна помощь с описанием работы данной проги, т.к. никак не могу разобраться что куда дописывать.
И нужно осуществить ввод веса ребер, и поиска кратчайшего пути по весу ребер.
Очень нужна помощь.
dejkstra.rar
Решение задачи: «Программа находит кратчайший путь по алгоритму Дейкстры, как разобраться в коде»
textual
Листинг программы
using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace ConsoleApplication18 { class Program { sealed public class Node { public List<Link> Links { get; set; } public Node() { Links = new List<Link>(); } } sealed public class Link { public double Distance { get; set; } public string Node { get; set; } } sealed public class Description { public bool Visited { get; set; } public double Distance { get; set; } public Description() { Visited = false; Distance = double.PositiveInfinity; } } sealed public class Graph { private Dictionary<string, Node> nodes; public Graph() { nodes = new Dictionary<string, Node>(); } public void AddNode(string name) { nodes.Add(name, new Node()); } public void AddLinkToNode(string start, string end, double distance, bool isOriented) { nodes[start].Links.Add(new Link { Node = end, Distance = distance }); if (!isOriented) nodes[end].Links.Add(new Link { Node = start, Distance = distance }); } public double FindShortestDistance(string start, string end) { // Алгоритм Дейкстры. Dictionary<string, Description> info = new Dictionary<string, Description>(this.nodes.Count); foreach (string current in this.nodes.Keys) info.Add(current, new Description()); info[start].Distance = 0; // Пока все вершины непосещенные. while (!info.Select(x => x.Value.Visited).Aggregate((x, y) => x & y)) { // Находим непосещенную вершину с минимальной меткой. string current = info.Where(x => !x.Value.Visited && x.Value.Distance == info.Where(y => !y.Value.Visited).Min(y => y.Value.Distance)) .First().Key; // Находим все непосещенные соседние вершины для текущей вершины. List<Link> neighbors = nodes[current].Links.Where(x => !info[x.Node].Visited).ToList(); // Рассматриваем новую длину пути для каждой соседней вершины. foreach (Link link in neighbors) { double distance = info[current].Distance + link.Distance; if (info[link.Node].Distance > distance) info[link.Node].Distance = distance; } // Отмечаем текущую вершину как посещенная. info[current].Visited = true; } return info[end].Distance; } } static void Main() { int count = 6; string[] names = { "A", "B", "C", "D", "E", "F" }; // Дан взвешенный ОРИЕНТИРОВАННЫЙ граф G(V,E) без петель и дуг отрицательного веса. // Найти кратчайшие пути от некоторой вершины a графа G до всех остальных вершин этого графа. // Все входные параметры методов данного графа считаются достоверными - нет проверок корректности параметров. Graph graph = new Graph(); // Заполнение графа вершинами. for (int i = 0; i < count; ++i) graph.AddNode(names[i]); // Создание у вершин связей. // Последнее значение говорит о том, что эта связь двунаправленная. graph.AddLinkToNode("A", "B", 7, false); graph.AddLinkToNode("A", "C", 9, false); graph.AddLinkToNode("A", "F", 14, false); graph.AddLinkToNode("B", "C", 10, false); graph.AddLinkToNode("B", "D", 15, false); graph.AddLinkToNode("C", "D", 11, false); graph.AddLinkToNode("C", "F", 2, false); graph.AddLinkToNode("D", "E", 6, false); graph.AddLinkToNode("E", "F", 9, false); Console.WriteLine(graph.FindShortestDistance("A", "B")); // Ответ 7. Console.WriteLine(graph.FindShortestDistance("A", "C")); // Ответ 9. Console.WriteLine(graph.FindShortestDistance("A", "D")); // Ответ 20. Console.WriteLine(graph.FindShortestDistance("A", "E")); // Ответ 20. Console.WriteLine(graph.FindShortestDistance("A", "F")); // Ответ 11. Console.ReadKey(); } } }
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д