Программа находит кратчайший путь по алгоритму Дейкстры, как разобраться в коде - 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();
        }
    }
}

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

11   голосов , оценка 4.273 из 5